フェルマーの小定理の証明問題
フェルマーの小定理とは
\(p\) が素数, \(n\) が任意の整数のとき
\(n^{p}\equiv n \pmod p\)
つまり, \(n^p-n\) は \(p\) の倍数
特に, \(n\) が \(p\) の倍数でないとき
\(n^{p-1}\equiv 1 \pmod p\)
つまり, \(n^{p-1}-1\) は \(p\) の倍数
大学入試でこの定理を覚える必要はないです。出題されるとしたら次の例題のような誘導でフェルマーの小定理を証明する問題が多いです。
例題:二項係数を用いた証明
問題
(1) \(r\) を \(p\) より小さい自然数とする。\({}_p\textrm{C}_{r}\) が \(p\) の倍数であることを証明せよ。
(2) \(n\) に関する数学的帰納法を用いて, \(n^p-n\) が \(p\) の倍数であることを証明せよ。
(3) \(n\) が \(p\) の倍数でないとき, \(n^{p-1}-1\) が \(p\) の倍数であることを証明せよ。
解答
\(\phantom{\Leftrightarrow}{}_p\textrm{C}_{r}=\dfrac{p(p-1)\cdots (p-r+1)}{r\,!}\\
\Leftrightarrow\, r\,!\,{}_p\textrm{C}_{r}=p(p-1)\cdots(p-r+1)\)
ゆえに, \( r\,!\,{}_p\textrm{C}_{r}\) は \(p\) の倍数である。
\(p\) は素数だから, \(p\) と \(r,r-1,\cdots ,1\) は互いに素。よって, \(r\,!\) は \(p\) の倍数ではない。
したがって, \({}_p\textrm{C}_{r}\,(1\leqq r \leqq p-1)\) は \(p\) の倍数である。(終)
補足
\(p\) が素数のとき, \(p\) と \(p\) より小さい自然数は互いに素です。
例えば, \(p=5\) のとき, \(5\) と\(4,3,2,1\) は互いに素であり, \(5\) と \(4\,!\) も互いに素です。
(2)
\(n^p-n\) が \(p\) の倍数であることを \(n\) に関する数学的帰納法を用いて証明する。
(i) \(n=1\) のとき
\(1^p-1=0\) は \(p\) の倍数である。
(ii) \(n=k\) のとき \(k^p-k\) が \(p\) の倍数であると仮定する。このとき
\(\phantom{=}(k+1)^p-(k+1) \\
=\displaystyle \sum_{r=0}^{p}\,{}_p\textrm{C}_{r}\,k^{p-r}-(k+1) \\
=\displaystyle\underbrace{ {}_p\textrm{C}_{0}\,k^p +\sum_{r=1}^{p-1}{}_p\textrm{C}_{r}\,k^{p-r} +{}_p\textrm{C}_{p}k^0}_{\sum から r=0,r=p の項を取り出した}-(k+1) \\
=\displaystyle k^p-k+\sum_{r=1}^{p-1}{}_p\textrm{C}_{r}\,k^{p-r} \)
仮定より \(k^p-k\) は \(p\) の倍数で, (1)より \({}_p\textrm{C}_{r}\,(1\leqq r \leqq p-1)\) は \(p\) の倍数であるから, \((k+1)^p-(k+1)\) も \(p\) の倍数である。
(i),(ii)より, すべての自然数 \(n\) に対して\(n^p-n\) は \(p\) の倍数である。(終)
(3)
(2)より, \( n^p-n=n(n^{p-1}-1)\) は \(p\) の倍数である。
\(n\) が \(p\) の倍数でないとき, \(n^{p-1}-1\) が \(p\) の倍数である。(終)