Lucasの定理とその証明

$i=0$ のときは両辺ともに $1+x$ となり成立。

$i=j$ のときに補題が成立すると仮定すると，

$$\begin{aligned} (1+x)^{p^{j+1}}&=\left\{(1+x)^{p^{j}}\right\}^p\\ &=(1+x^{p^j})^p \end{aligned}$$

ここで，上式を二項定理で展開すると ${}_{p}\mathrm{C}_{t}\:(1\leq t\leq p-1)$ は全て $p$ の倍数（→注）なので，$\mathrm{mod}\:p$ では $1+x^{p^{j+1}}$ と等しい。

つまり $i=j+1$ のときにも補題が成立する。帰納法によりOK。

任意の $t\:(1\leq t\leq p^i-1)$ に対して ${}_{p^i}\mathrm{C}_t$ が $p$ の倍数であることを示せばよい。

$$t\cdot {}_{p^i}\mathrm{C}_t=p^i\cdot{}_{p^i-1}\mathrm{C}_{t-1}$$

において，右辺は $p^i$ の倍数なので左辺も $p^i$ の倍数。$t < p^i$ より，$t$ が持つ素因数 $p$ の個数は $i-1$ 以下。よって，${}_{p^i}\mathrm{C}_t$ は $p$ の倍数。

$(1+x)^m$ を展開したときの $x^n$ の係数を2通りの方法で考える。まず，二項定理より，これは ${}_{m}\mathrm{C}_{n}$ である。

一方，$m$ の $p$ 進数表示を使うと，

$$\begin{aligned} &(1+x)^m\\ &=(1+x)^{m_kp^{k}}(1+x)^{m_{k-1}p^{k-1}}\cdots (1+x)^{m_1p}(1+x)^{m_0} \end{aligned}$$

さらに補題を使うと，上式は $\mathrm{mod}\:p$ で

$$(1+x^{p^k})^{m_k} (1+x^{p^{k-1}})^{m_{k-1}}\cdots (1+x^{p})^{m_1} (1+x)^{m_0}$$

と等しい。

この式について，$x^n$ という項がどのように登場するか考えると，

1つめの因数部分から $x^{n_kp^k}$，2つめの因数部分から $x^{n_{k-1}p^{k-1}}$，$\cdots$，最後の因数部分から $x^{n_0}$ を取ってきたもののみなので，その係数は

$$\prod_{i=0}^k{}_{m_i}\mathrm{C}_{n_i}$$

となる（$m_i < n_i$ となる $i$ が存在する場合，$x^n$ という項は存在しない，これは ${}_{m_i}\mathrm{C}_{n_i}=0$ であることと整合する）。