n, r이 자연수라면 반드시 nCr은 자연수가 나옵니다. 이를 증명하기 위해서는 연속된 m개의 자연수 중에는 반드시 m의 배수가 존재한다는 성질을 이용해야 합니다. 연속된 m개의 자연수 중 가장 작은 수를 n이라 하면, n+m-1이 가장 큰 숫자입니다. 여기서 n을 m으로 나눈 나머지를 r이라고 하면, n = mq + r 의 형태로 표현할 수 있습니다. 이 때, r의 범위는 0≤r≤m-1 입니다. r=0 이면, n이 m의 배수이고, r=1 이면, n + m-1 =mq + 1 + m-1 = mq + m = m(q+1) 이므로, n+m-1 이 m의 배수, r=2 이면, n + m - 2 = mq + 2 + m-2 = mq+m = m(q+1) 이므로, n+m-2 가 m의 배수가 되며, 0≤k≤m-1 인 어떤 자연수 k에 대해서 n을 m으로 나눈 나머지가 k일 때, n = mq + k 가 되어, n + m - k = mq + k + m - k = mq+m = m(q+1) 이 m의 배수가 되기 때문에 연속된 m개의 자연수에 대해서 반드시 m의 배수가 존재하게 됩니다. nCr = n!/r!(n-r)! = n×(n-1)×…×(n-r+1)/r×(r-1)×…×2×1 입니다. 이 때, 분자는 연속된 r개의 자연수의 곱으로 이루어져 있고, 분모는 1부터 r까지 모든 자연수가 곱해져 있습니다. 앞서 말했던 성질에 의해서 분자에 곱해진 r개의 자연수 중에는 반드시 r의 배수가 존재하기 때문에 분모의 r을 약분할 수 있고, r>r-1 이므로, r개의 자연수 중에서는 r-1 의 배수가 1개 이상 존재하며, 비슷하게 분모에 곱해진 모든 수에 대해서 해당 수에 대한 배수가 존재하기 때문에 분모가 모두 약분됩니다. 따라서 분모가 모두 약분되기 때문에 nCr은 반드시 자연수가 됩니다.