解答例 1

二項係数が整数であることは認めることにする.

$n$ に関する数学的帰納法により証明する.

$n=1$ のとき, $\displaystyle\binom{p}{r}$ が $p$ で割れることは既知であるとし, 証明は省略する.

$n>1$ とし, $n-1$ のとき問題の主張が正しいと仮定する. $r$ は, ある整数 $m$, $l$ によって, $$ r = pm+l,\quad 0\leq l<p $$ と表せる. さて, $l=0$ の場合, $1\leq r\leq p^{n}-1$ より $1\leq m\leq p^{n-1}-1$ である. また, \begin{align*} \binom{p^{n}}{r} &= \frac{p^{n}(p^{n}-1)(p^{n}-2)\cdots(p^{n}-pm+1)}{(pm)!} \\ &= \prod_{k=0}^{m-1}\frac{(p^{n}-kp)(p^{n}-kp-1)\cdots(p^{n}-(k+1)p+1)} {(pm-kp)(pm-kp-1)\cdots(pm-(k+1)p+1)} \\ &= \prod_{k=0}^{m-1}\frac{p^{n}-kp}{pm-kp} \prod_{k=0}^{m-1}\frac{(p^{n}-kp-1)\cdots(p^{n}-(k+1)p+1)} {(pm-kp-1)\cdots(pm-(k+1)p+1)}. \end{align*} 帰納法の仮定を用いると, \begin{align*} \prod_{k=0}^{m-1}\frac{p^{n}-kp}{pm-kp} &= \prod_{k=0}^{m-1}\frac{p^{n-1}-k}{m-k} \\ &= \binom{p^{n-1}}{m}\equiv 0\pmod{p}. \end{align*} 一方, \begin{align*} &\prod_{k=0}^{m-1}\frac{(p^{n}-kp-1)\cdots(p^{n}-(k+1)p+1)} {(pm-kp-1)\cdots(pm-(k+1)p+1)} \\ &\equiv\prod_{k=0}^{m-1}\frac{(p-1)!}{(p-1)!} = 1\pmod{p}. \end{align*} $1\leq l<p$ の場合, \begin{align*} \binom{p^{n}}{r} &= \frac{p^{n}(p^{n}-1)(p^{n}-2)\cdots(p^{n}-(pm+l)+1)}{(pm+l)!} \\ &= \binom{p^{n}}{pm}\cdot \frac{(p^{n}-pm)(p^{n}-pm-1)\cdots(p^{n}-pm-l+1)}{(pm+l)(pm+l-1)\cdots(pm+1)}. \end{align*} 分母の $(pm+l)(pm+l-1)\cdots(pm+1)$ は $p$ で割れないから, $\displaystyle\binom{p^{n}}{r}\equiv 0\pmod{p}$ となる. よって, $n$ のときも問題の主張は成り立つ.

したがって, すべての正の整数 $n$ に対して問題の主張は正しいことが証明された.

解答例 2

$p$ を素数とし, $\mathbb{F}_p$ を $p$ 個の元からなる有限体とする. 多項式環 $\mathbb{F}_p[X]$ において, $$ (1+X)^{p^{n}} = 1^{p^{n}} + X^{p^{n}} = 1 + X^{p^{k}}. $$ 一方, 二項定理より, $$ (1+X)^{p^n} = \sum_{k=0}^{p^n}\binom{n}{k}X^{k}. $$ ゆえに, $$ 1 + X^{p^{n}} = \sum_{k=0}^{p^n}\binom{n}{k}X^{k}. $$ $X^{r}$ の係数を比較すると, $\displaystyle\binom{p^{n}}{r}\equiv 0\pmod{p}$ が得られる.

最終更新日：2011年11月02日