数学A フェルマーの小定理 問題 3 解説

方針・初手

二項係数の基本公式

$$ {}_pC_k=\frac{p!}{k!(p-k)!} $$

を用いて、まず ({}pC_k) と ({}{p-1}C_{k-1}) の関係を作る。次に、$p$ が素数であることから $1\leqq k\leqq p-1$ では $k$ と $p$ が互いに素であることを利用する。

解法1

まず、$1\leqq k\leqq p$ とする。このとき

$$ \begin{aligned} {}*{p-1}C*{k-1} &= \frac{(p-1)!}{(k-1)!(p-k)!} \end{aligned} $$

であるから、

$$ \begin{aligned} p\cdot {}*{p-1}C*{k-1} &= p\cdot \frac{(p-1)!}{(k-1)!(p-k)!} \\ \frac{p!}{(k-1)!(p-k)!} \end{aligned} $$

となる。

一方、

$$ \begin{aligned} k\cdot {}_pC_k &= k\cdot \frac{p!}{k!(p-k)!} \end{aligned} $$

であり、$k!=k(k-1)!$ より

$$ \begin{aligned} k\cdot {}_pC_k &= k\cdot \frac{p!}{k(k-1)!(p-k)!} \\ \frac{p!}{(k-1)!(p-k)!} \end{aligned} $$

となる。

したがって

$$ \begin{aligned} p\cdot {}*{p-1}C*{k-1} &= k\cdot {}_pC_k \end{aligned} $$

が成り立つ。これで （1） が示された。

次に、$1\leqq k\leqq p-1$ とする。（1） より

$$ \begin{aligned} k\cdot {}_pC_k &= p\cdot {}*{p-1}C*{k-1} \end{aligned} $$

である。右辺は $p$ の倍数だから、左辺 $k\cdot {}_pC_k$ も $p$ の倍数である。

ここで $p$ は素数であり、$1\leqq k\leqq p-1$ だから、$k$ は $p$ の倍数ではない。よって $k$ と $p$ は互いに素である。

したがって、$p$ が $k\cdot {}_pC_k$ を割り、かつ $p$ と $k$ が互いに素であることから、$p$ は ({}_pC_k) を割る。

ゆえに

$$ {}_pC_k $$

は $p$ の倍数である。これで （2） が示された。

最後に、二項定理より

$$ \begin{aligned} 2^p=(1+1)^p &= \sum_{k=0}^{p}{}_pC_k \end{aligned} $$

である。これを端の項と中間の項に分けると、

$$ \begin{aligned} 2^p &= {}_pC_0+{}*pC_p+\sum*{k=1}^{p-1}{}_pC_k \end{aligned} $$

となる。

ここで

$$ {}_pC_0=1,\qquad {}_pC_p=1 $$

だから、

$$ \begin{aligned} 2^p &= 2+\sum_{k=1}^{p-1}{}_pC_k \end{aligned} $$

である。

（2） より、$1\leqq k\leqq p-1$ に対して ({}_pC_k) はすべて $p$ の倍数である。したがって、その和

$$ \sum_{k=1}^{p-1}{}_pC_k $$

も $p$ の倍数である。

よって

$$ \begin{aligned} 2^p-2 &= \sum_{k=1}^{p-1}{}_pC_k \end{aligned} $$

は $p$ の倍数である。これで （3） が示された。

解説

この問題は、二項係数の性質からフェルマーの小定理の特別な場合

$$ 2^p\equiv 2 \pmod p $$

を導く問題である。

重要なのは、({}_pC_k) を直接計算するのではなく、まず

$$ \begin{aligned} p\cdot {}*{p-1}C*{k-1} &= k\cdot {}_pC_k \end{aligned} $$

という関係式を作ることである。これにより、({}_pC_k) の分子に含まれる $p$ の因子を、割り切れの形で扱える。

また、（2） では $1\leqq k\leqq p-1$ という条件が本質的である。この範囲では $k$ は $p$ の倍数ではないため、$k$ と $p$ は互いに素である。そのため、$p\mid k{}_pC_k$ から $p\mid {}_pC_k$ が言える。

最後の （3） は二項定理で $2^p=(1+1)^p$ と展開し、中間項がすべて $p$ の倍数であることを使うのが標準的な流れである。

答え

(1)

$$ \begin{aligned} p\cdot {}*{p-1}C*{k-1} &= k\cdot {}_pC_k \end{aligned} $$

が成り立つ。

(2)

$1\leqq k\leqq p-1$ のとき、

$$ {}_pC_k $$

は $p$ の倍数である。

(3)

$$ 2^p-2 $$

は $p$ の倍数である。