Without loss of generality, assume i,j <= n/2. From the identity C(n,i) C(n-i,j) = C(n,j) C(n-j,i), it follows that if C(n,i) and C(n,j) are relatively prime, then C(n,i) divides C(n-j,i), a contradiction since C(n,i) > C(n-j,i) > 0.