陥没地帯 (250) - ノリの悪い日記

記事 $(24)$ の問題 ( $1999$ 年東大) の問題を前回の二項定理を使った方法で解き直す. 前のよりはだいぶすっきりしたなあ.

念のため, 基本定理の証明を最初にしておく.

【基本定理】
標数 $p > 0$ の素体 *1 の任意の要素 $a$ , $b$ について,

$(a + b)^p = a^p + b^p$

が成立する。

【証明】
左辺を二項定理で展開したときの $a^p, b^p$ 以外の各項は, ${}_p\mathrm{C}_n a^nb^{p-n}$ となるが,

$p! = {}_p\mathrm{C}_nn!(p-n)! \equiv 0 \pmod{p}$

で, $p$ が素数であることから,

$n! \not\equiv 0 \pmod{p}$
$(p-n)! \not\equiv 0 \pmod{p}$

である. したがって,

${}_p\mathrm{C}_n \equiv 0 \pmod{p}$

体の単位元を $e$ とすれば, ${}_p\mathrm{C}_ne = 0$ なので,

$\displaystyle{(a+ b)^p = \sum_{k=0}^{p} {}_p\mathrm{C}_ka^kb^{n-k} = a^p + b^p }$

となる. //

【系】
上の定理で, $N$ を自然数とすると,

$\displaystyle{(a + b)^{p^N} = a^{p^N} + b^{p^N}}$

が成立する.

【証明】
$N=1$ のとき, 上の定理そのものなので成立する. $N$ で成立すると仮定すると,

$(a + b)^{p^{N+1}} \\= (a^{p^N} + b^{p^N})^p \\= a^{p^{N+1}} + b^{p^{N+1}}$

となって成立する.
//

次からが, 入試問題.

【問】
$\text{(1)}$ $k$ を自然数とする. $m$ を $m = 2^k$ とおくとき, $0 < n < m$ をみたすすべての整数 $n$ について, 二項係数 $_m \mathrm{C}_{n}$ は偶数であることを示せ.

$\text{(2) }$ 以下の条件をみたす自然数 $m$ をすべて求めよ.

条件: $0 \leq n \leq m$ をみたすすべての整数 $n$ について二項係数 $_m \mathrm{C}_n$ は奇数である.

【解】
$(1)$
題意が成り立つことは, 法 $2$ の剰余整数を係数とする多項式を考えたとき,

$(x+1)^m = x^m + 1$

であることをいうのと同じである.

$m = 2^k$ のとき, 上の定理の系からこれは成立する.

※ $m \neq 2^k$ であれば, $q>1$ の奇数を使って $m = 2^kq$ と書けるので,

$(x+1)^{2^kq} \\= (x^{2^k}+1)^q \\= x^{2^kq} + qx^{2^k(q-1)} + \cdots + 1$

だが, $q \equiv 1 \pmod{2}$ なので, $(x+1)^m \neq x^m + 1$ である.

したがって, $m = 2^k$ であることは, 二項係数 $_m \mathrm{C}_{n}$ がすべての $0 < n < m$ で偶数であるための必要十分条件であることがいえた.

$(2)$
パスカルの三角形を法 $2$ で作ると,

$\begin{matrix} 1:&1&1\\ 2:&1&0&1\\ 3:&1&1&1&1\\ 4:&1&0&0&0&1\\ 5:&1&1&0&0&1&1\\ 6:&1&0&1&0&1&0&1\\ 7:&1&1&1&1&1&1&1&1\\ 8:&1&0&0&0&0&0&0&0&1\\ \end{matrix}$