Lucasの定理(二項係数)

$i$ についての数学的帰納法で示す。$i=0$ は明らかである。二項定理から $(1+T)^p=\sum_{j=0}^p\binom pjT^j$ であり、$0< j< p$ では $\binom pj=\dfrac{p!}{j!\,(p-j)!}$ の分子は $p$ で割り切れ、分母は $p$ で割り切れないので、$\binom pj\equiv0\pmod p$ である（二項係数 の命題「素数に関する合同式」）。よって $(1+T)^p=1+T^p$ である。$i$ で主張が成り立つとすると、同じ式の $T$ に $T^{p^i}$ を代入した $(1+T^{p^i})^p=1+T^{p^{i+1}}$ から
$$ (1+T)^{p^{i+1}}=\bigl((1+T)^{p^i}\bigr)^p=(1+T^{p^i})^p=1+T^{p^{i+1}} $$
となる。$\square$

$\mathbb{F}_p[T]$ で $(1+T)^n$ を 2 通りに書く。まず $(1+T)^n=\sum_{m\ge0}\binom nmT^m$ である。次に $n=\sum_in_ip^i$ と lem-lt-frobenius から
$$ (1+T)^n=\prod_{i=0}^{s}\bigl((1+T)^{p^i}\bigr)^{n_i}=\prod_{i=0}^{s}\bigl(1+T^{p^i}\bigr)^{n_i}=\prod_{i=0}^{s}\left(\sum_{j_i=0}^{n_i}\binom{n_i}{j_i}T^{j_ip^i}\right) $$
である。右辺を展開すると、各項は組 $(j_0,\dots,j_s)$（$0\le j_i\le n_i$）ごとに
$$ \binom{n_0}{j_0}\binom{n_1}{j_1}\cdots\binom{n_s}{j_s}\,T^{\,j_0+j_1p+\dots+j_sp^s} $$
となる。$0\le j_i\le n_i\le p-1$ なので、指数 $j_0+j_1p+\dots+j_sp^s$ は $j_0,\dots,j_s$ を桁とする $p$ 進表示であり、$p$ 進表示の一意性から、異なる組は異なる指数を与える。
$T^k$ の係数を比べる。すべての $i$ で $k_i\le n_i$ なら、指数が $k$ になる組は $(j_i)=(k_i)$ ただ 1 つなので、右辺の $T^k$ の係数は $\prod_i\binom{n_i}{k_i}$ である。ある $i$ で $k_i>n_i$ なら、指数が $k$ になる組はない（あれば一意性から $j_i=k_i>n_i$ となる）ので、右辺の $T^k$ の係数は $0$ であり、これは $\binom{n_i}{k_i}=0$ を因子にもつ $\prod_i\binom{n_i}{k_i}$ に等しい。どちらの場合も左辺の係数 $\binom nk$ と法 $p$ で合同なので、主張を得る。$\square$

ある $i$ で $k_i>n_i$ なら、右辺は $0$ なので $p\mid\binom nk$ である。すべての $i$ で $k_i\le n_i$ のとき、$n_i\le p-1$ なので $n_i!$ は $p$ で割り切れず、$\binom{n_i}{k_i}\,k_i!\,(n_i-k_i)!=n_i!$ から $\binom{n_i}{k_i}$ も $p$ で割り切れない。$p$ は素数なので、$p$ で割り切れない数の積も $p$ で割り切れず、thm-lt-main により $\binom nk$ は $p$ で割り切れない。$\square$

cor-lt-nonzero により、数えるのは $0\le k\le n$ で、すべての桁で $k_i\le n_i$ となる $k$ である。桁を $0\le k_i\le n_i$ の範囲で自由に選んだ $k=\sum_ik_ip^i$ は $k\le n$ を満たし、$p$ 進表示の一意性から異なる選び方は異なる $k$ を与える。逆に $0\le k\le n$ の $p$ 進表示は第 $s$ 桁までで済む。よって数える $k$ は、各 $i$ で $k_i$ を $n_i+1$ 通りから選ぶ組と 1 対 1 に対応する。$\square$

1 は cor-lt-nonzero の $p=2$ の場合である（桁は $0$ か $1$ なので、$k_i\le n_i$ が破れるのは $k_i=1$、$n_i=0$ のときに限る）。2 は cor-lt-count で、$n_i+1$ が $n_i=1$ の桁では $2$、$n_i=0$ の桁では $1$ になることによる。3：すべてが奇数であることは、2 により $2^{b(n)}=n+1$ と同値である。$n\ge1$ の二進表示の桁数を $m$ とすると $2^{m-1}\le n$ かつ $b(n)\le m$ である。$2^{b(n)}=n+1$ なら $2^{b(n)}>2^{m-1}$ なので $b(n)=m$ となり、$m$ 個の桁がすべて $1$、すなわち $n=2^m-1$ である。逆に $n=2^m-1$ なら二進表示は $m$ 個の $1$ で、$2^{b(n)}=2^m=n+1$ である。$n=0$ は $m=0$ にあたり、$\binom00=1$ は奇数である。$\square$

整数係数の多項式で考える。$0< j< p$ では $\binom pj$ は $p$ で割り切れる（prf-lt-frobenius）ので、
$$ (1+T)^p=1+T^p+pF(T),\qquad F(T):=\sum_{j=1}^{p-1}\frac1p\binom pjT^j $$
と書け、$F$ は整数係数で、現れる $T$ の指数はどれも $p$ の倍数でない。二項定理から
$$ (1+T)^{pa}=\bigl((1+T^p)+pF(T)\bigr)^a=\sum_{j=0}^{a}\binom aj\,p^j\,F(T)^j\,(1+T^p)^{a-j} $$
であり、$j\ge2$ の項の係数はすべて $p^2$ で割り切れる。$j=0$ の項 $(1+T^p)^a$ の $T^{pb}$ の係数は $\binom ab$ である。$j=1$ の項 $ap\,F(T)(1+T^p)^{a-1}$ では、$F(T)$ の各項の指数は $p$ の倍数でなく、$(1+T^p)^{a-1}$ の各項の指数は $p$ の倍数なので、積の各項の指数は $p$ の倍数でない。よってこの項は $T^{pb}$ を含まない。以上から $(1+T)^{pa}$ の $T^{pb}$ の係数 $\binom{pa}{pb}$ は、法 $p^2$ で $\binom ab$ と合同である。$\square$

1：$N:=p^r$ とおく。$0$ 以上の整数 $x$ については、$(1+T)^{x+N}=(1+T)^x(1+T)^N$ の $T^k$ の係数を比べて
$$ \binom{x+N}k=\sum_{j=0}^{k}\binom Nj\binom x{k-j} $$
を得る（Vandermonde の公式）。両辺は $x$ の多項式で、$0$ 以上のすべての整数 $x$ で一致するので、多項式として等しく、すべての整数 $x$ で成り立つ。$0< j\le k< p^r$ では、節「例」の最後に見たとおり $p\mid\binom{p^r}j$ なので、
$$ \binom{x+N}k\equiv\binom xk\pmod p $$
がすべての整数 $x$ で成り立つ。これを $x$ の増える向きと減る向きに繰り返し使えば、$x\equiv a\pmod N$ のとき $\binom xk\equiv\binom ak\pmod p$ である。
2：$\binom{-c}k=(-1)^k\binom{c+k-1}k$ であり、$n:=c+k-1$ とおくと $0\le k\le n$、$n-k=c-1$ である。cor-lt-nonzero と、その後に見た「すべての桁で $k_i\le n_i$ であることは、$k$ と $n-k$ の足し算に繰り上がりがないことと同値」から主張を得る。$\square$