二項係数（組み合わせの数）が整数になることの証明をメモしておきます。
これについて、2通りの証明法が知られています。
${}_{n}\mathrm{C}_{m}$ が整数であることの証明
① 素因数の個数に着目した証明
② 数学的帰納法による証明
$${}_{n}\mathrm{C}_{m}=\dfrac{n!}{m!(n-m)!} \quad \cdots (*)$$が整数になることを示すには、連続する$m$個の整数の積$$\small n(n-1)\cdots(n-m+1)=\dfrac{n!}{(n-m)!}$$が$m!$で割り切れることを示せば十分です。
証明①では「ルジャンドルの定理」を利用し、分子と分母の素因数の個数を評価して示します。証明②ではいわゆる「強化帰納法」を用います。
証明①
$(*)$の分子 $n!$ に含まれる素因数 $p$ の個数は$$\small \displaystyle\sum_{i=1}^{\infty}\left[ \dfrac{n}{p^i} \right]$$であり、$(*)$の分母 $m!(n-m)!$ に含まれる素因数 $p$ の個数は$$\small \displaystyle\sum_{i=1}^{\infty}\left(\left[ \dfrac{m}{p^i} \right]+\left[ \dfrac{n-m}{p^i} \right]\right)$$となる（ルジャンドルの定理による）。
ガウス記号について一般に$$[x+y] \geqq [x]+[y]$$が成り立つから、$$\small \displaystyle \sum_{i=1}^{\infty}\left[ \dfrac{n}{p^i} \right] \geqq \sum_{i=1}^{\infty}\left(\left[ \dfrac{m}{p^i} \right]+\left[ \dfrac{n-m}{p^i} \right]\right)$$となる。これがすべての素因数 $p$ について成り立つから、 $(*)$の分子に含まれる素因数 $p$ の個数は$(*)$の分母よりも多い。故に、連続する $m$ 個の整数の積は $m!$ で割り切れる。
したがって、$${}_{n}\mathrm{C}_{m}=\dfrac{n!}{m!(n-m)!}$$は整数であることが示された。
□
この方針による証明は非常に簡明です。証明中で用いた不等式$$[x+y] \geqq [x]+[y] \quad \cdots (★)$$は以下のように証明可能です。
不等式$(★)$の証明
$[x]=m$、$[y]=n$ $(m, n \in Z)$ と置くと、ガウス記号の定義より$$\begin{cases}
m \leqq x<m+1 \\
n \leqq y<n+1
\end{cases}$$が成り立つ。これより辺々を加えると$$m+n \leqq x+y<m+n+2$$となるから$$[x+y]=m+n \text{ または } m+n+1$$を得る。一方で $[x]+[y]=m+n$ であるから、$$[x+y] \geqq [x]+[y]$$が成立する。
□
証明②
連続する$m$個の整数の積$$\small \mathrm{P}(n,m)=n(n+1)\cdots(n+m-1)$$が $m!$ で割り切れることを数学的帰納法で証明する。
$n=1$ のとき、および $m=1$ のときは明らかに $\mathrm{P}(n,m)$ が $m!$ で割り切れる。
以下、$n+m$ に関する数学的帰納法で証明する。$n+m \leqq N$ のとき $\mathrm{P}(n,m)$ が $m!$ で割り切れると仮定して、$n+m=N+1$ の場合を考える。
$n=1$ や $m=1$ のときは成り立つから、$n>1$、$m>1$ としてよい。$\mathrm{P}(n,m)$は$$\small \begin{align} & \quad \ \mathrm{P}(n,m) \\ &=n(n+1)\cdots(n+m-1) \\ &=n(n+1)\cdots(n+m-2)(n-1) \\ & \quad \quad +n(n+1)\cdots(n+m-2)m \\ &=(n-1)n(n+1)\cdots(n-1+m-1) \\ & \quad \quad +n(n+1)\cdots(n+m-1-1)m \\ &=\mathrm{P}(n-1,m)+\mathrm{P}(n,m-1)\cdot m\end{align}$$と変形できる。いま、$(n-1)+m=n+(m-1)=N$ であるから、帰納法の仮定より $\mathrm{P}(n-1,m)$ は $m!$ で割り切れ、$a(n,m-1)$ は $(m-1)!$ で割り切れる。
よって $\mathrm{P}(n,m-1)m$は、$m!$で割り切れるから、$\mathrm{P}(n,m)$は$m!$で割り切れる。これより、$n+m=N+1$ の場合でも仮定が成立するから、数学的帰納法によりすべての $n$、$m$ について $\mathrm{P}(n,m)=n(n+1)\cdots(n+m-1)$ は $m!$ で割り切れる。
したがって、$${}_{n}\mathrm{C}_{m}=\dfrac{n!}{m!(n-m)!}$$は整数であることが示された。
□
上の証明では積 $\mathrm{P}(n,m)$ を考えましたが、二項係数のまま議論を進めると以下のようになります。
証明②（改）
$${}_{n}\mathrm{C}_{m}=\dfrac{n!}{m!(n-m)!} \quad \cdots (*)$$が整数になることを$n$についての帰納法で示す。以下、$0!=1$ と定める。
$n=1$ のとき、明らかに ${}_{n}\mathrm{C}_{m}$ は $n!$ で割り切れる。
$n=k$ のとき、$1 \leqq m \leqq k$ を満たすすべての $m$ について ${}_{n}\mathrm{C}_{m}$ が整数だと仮定する。二項係数について成り立つ以下の関係式$${}_{k+1}\mathrm{C}_{m}={}_{k}\mathrm{C}_{m}+{}_{k}\mathrm{C}_{m-1}$$および仮定より、$1 \leqq m \leqq k$ を満たすすべての $m$ について ${}_{k+1}\mathrm{C}_{m}$ も整数となる。また、$${}_{k+1}\mathrm{C}_{0}={}_{k+1}\mathrm{C}_{k+1}=1$$であり整数となる。よって、$n=k+1$ のときも$(*)$は整数になる。
したがって、数学的帰納法により$(*)$が整数であることが示された。
□
これらの他に「二項係数${}_{n}\mathrm{C}_{m}$は組み合わせを取ったときの総数を表すから整数」という証明もあり得ますが、これが自明だと感じられない人も多いかと思い、証明法をまとめてみました。帰納法だとやや答案風に書くのが手間でしょうか。入試ではこの証明はまともに出題されませんが、やり方を知っておくといざという時に役立ちます。