フェルマーの小定理を帰納法によって証明する例題です。
(例題)
\(n\)を自然数、\(p\)を素数とするとき
(1)\({}_p\mathrm{C}_{r}\) (\(r\)は自然数で、\(1≦r≦p-1\)) は\(p\)の倍数であることを示せ。
(2)\(n^{p}-n\) は\(p\)の倍数であることを示せ。
(3)\(n\)と\(p\)が互いに素であるとき、\(n^{p-1}-1\) は\(p\)の倍数であることを示せ。
(解答)
(1)
\(r\cdot{}_p\mathrm{C}_{r}=p\cdot{}_{p-1}\mathrm{C}_{r-1}\) を利用するか、\({}_p\mathrm{C}_{r}\) を階乗の式に変形するかになります。最初の等式は階乗の式に変形して証明できますが、意味としては「\(p\)人から\(r\)人選んでその中から代表を1人決める方法は、先に代表を1人選んで残りの\(p-1\)人から\(r-1\)人選ぶ方法と等しい」ということです。
\(p\)は素数で、\(r\)は\(1\)以上\(p-1\)以下の整数だから、\(p\)と\(r\)は互いに素である。
よって等式
\(r\cdot{}_p\mathrm{C}_{r}=p\cdot{}_{p-1}\mathrm{C}_{r-1}\)
より、\(r\cdot{}_p\mathrm{C}_{r}\)は\(p\)の倍数だから、\({}_p\mathrm{C}_{r}\)は\(p\)の倍数。
(2)
「\(n^{p}-n\) は\(p\)の倍数 (\(p\)は素数) 」を数学的帰納法で示す。
[1]\(n=1\) のとき
\(1^{p}-1=0=p×0\) より\(p\)の倍数。
[2]\(n=k\) のとき (\(k=1,2,3,\cdots\))
\(k^{p}-k\) が\(p\)の倍数であると仮定すると
\(k^{p}-k=pL\) (\(L\)は整数)
とおける。
このとき \(n=k+1\) では
\((k+1)^{p}-(k+1)\)
\(=k^{p}+{}_p\mathrm{C}_{1}k^{p-1}+{}_p\mathrm{C}_{2}k^{p-2}+\cdots+{}_p\mathrm{C}_{p-1}k+1-(k+1)\)
\(=({}_p\mathrm{C}_{1}k^{p-1}+{}_p\mathrm{C}_{2}k^{p-2}+\cdots+{}_p\mathrm{C}_{p-1}k)+k^{p}-k\)
((1)と\(n=k\)の仮定から \(M\)を整数として)
\(=pM+pL\)
\(=p(M+L)\)
よって\(n=k+1\)のときも\(p\)の倍数となる。
[1][2]よりすべての自然数で\(n^{p}-n\) は\(p\)の倍数である。
(3)
(2)より
\(n^{p}-n=pG\) (\(G\)は整数)
と表せ
\(n(n^{p-1}-1)=pG\)
\(n\)と\(p\)が互いに素であるから、\(n^{p-1}-1\)は\(p\)の倍数である。
以上になります。お疲れさまでした。
ここまで見ていただきありがとうございました。
next→n=k,k+1の仮定 back→命題の証明と帰納法