フェルマーの小定理は初等整数論の最強武器の一つです。
マジで最強です。
しかし、天下り的に定理と証明を与えられても、
いまいちその美しさが伝わりにくいものです。
そこで、今回の記事では具体例を観察しながらこの最強武器を再発見していこうと思います。
等比数列と合同式
２，４，８，１６，３２，６４，１２８，$\cdots$
という数の並びを観察していきます。
これは、２倍、２倍、２倍$\cdots$
というルールに支配された数の並びで、等比数列といいます。
これを合同式の世界で観察してみましょう。
$2 \equiv 0 (\mod 2)$
$2\equiv 2,$ $2^2 \equiv 1 (\mod 3)$
$2 \equiv 0,$ $2^2 \equiv 0, $ $2^3 \equiv 0(\mod 4)$
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 3,$ $2^4 \equiv 1(\mod 5)$
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 2,$ $2^4 \equiv 4,$ $2^5 \equiv 2(\mod 6)$
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 1,$ $2^4 \equiv 2,$ $2^5 \equiv 4,$ $2^6 \equiv 1(\mod 7)$
$2\equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 0,$ $2^4 \equiv 0,$ $2^5 \equiv 0, $ $2^6 \equiv 0 ,$ $2^7 \equiv 0 (\mod 8)$
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 8,$ $2^4 \equiv 7,$ $2^5 \equiv 5,$ $2^6 \equiv 1,$ $2^7 \equiv 2,$ $2^8 \equiv 4 (\mod 9)$
$2\equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 8,$ $2^4 \equiv 6 ,$ $2^5 \equiv 2,$ $2^6 \equiv 4,$ $2^7 \equiv 8,$ $2^8 \equiv 6,$ $2^9 \equiv 2 (\mod 10)$
$2\equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 8,$ $2^4 \equiv 5,$ $2^5 \equiv 10,$ $2^6 \equiv 9,$ $2^7 \equiv 7 ,$ $2^8 \equiv 3,$ $2^9 \equiv 6$ $2^{10} \equiv 1 (\mod 11)$
何か規則性は見えましたか？
中々難しいと思います。
そこで、規則性を見つける際のスペシャルツールを使いましょう。
それは、分類する、という手法です。
すべての場合に通用するルールが見えなくとも、
ある特定の範囲については共通の性質がある、ということは結構あります。
そこが研究の突破口になるのです。
今回は、ひとまず3つのグループに分類してみました。
① ０が出るグループ
② 最後が１で終わるグループ
③ それ以外
それぞれもう少し細かく観察していきましょう。
① ０が出るグループ
$2, 2^2, 2^3, 2^4, \cdots$
について、
$\mod 2$ $\mod 4$ $\mod 8$
は途中から０ばかりになります。
よくよく考えればこれは当り前のことですね。
2倍、2倍、2倍の等比数列で、法を２の倍数に取っているので、
そりゃ途中で割った余りが０になるに決まっています。
これを文字を使って表すと、次のようになります。
$a, b$を自然数とする。
$a$が$b$の倍数であるとき、
$a, a^2, a^3, \cdots$
を$b$を法として並べたとき、
$a^n \equiv 0 (\mod b)$となるものが存在する。
さて。
本番はこっからです。
② 最後が１で終わるグループ
観察結果から、最後が１で終わるものだけ取り出してみましょう。
$2\equiv 2,$ $2^2 \equiv 1 (\mod 3)$
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 3,$ $2^4 \equiv 1(\mod 5)$
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 1,$ $2^4 \equiv 2,$ $2^5 \equiv 4,$ $2^6 \equiv 1(\mod 7)$
$2\equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 8,$ $2^4 \equiv 5,$ $2^5 \equiv 10,$ $2^6 \equiv 9,$ $2^7 \equiv 7 ,$ $2^8 \equiv 3,$ $2^9 \equiv 6$ $2^{10} \equiv 1 (\mod 11)$
$\mod 3$ $\mod 5$ $\mod 7$ $\mod 11$
見事に全て素数です。
$\mod 7$は最後だけじゃなくて途中にも１が出てますが、まぁ最後が１であるという点は共通なのでよしとしましょう。
観察結果の最後の部分だけ取り出すと、
$2^2 \equiv 1 (\mod 3)$
$2^4 \equiv 1 (\mod 5)$
$2^6 \equiv 1(\mod 7)$
$2^{10}\equiv 1 (\mod 11)$
です。
①のグループを除外して、
これらを文字で表すと、こんな予想が成り立ちそうです。
$p$が素数で、$a$が$p$の倍数ではない整数のとき、
$a^{p-1} \equiv 1(\mod p)$
が成り立つ
これこそが、いわゆるフェルマーの小定理です。
フェルマーの名を関するものでは、フェルマーの最終定理が有名ですが、それとは別物です
（フェルマーの最終定理はピタゴラス数の一般化で、$a^n+b^n=c^n$となる正の整数$a, b, c$は、$n$が$3$以上では存在しない、というもの。$n=2$の場合はピタゴラス数そのもの。いつかフェルマーの最終定理に関する記事も書いてみたいなぁと夢見る今日この頃です。フェルマーの最終定理の証明はワイルズさんというイギリスの天才数学者が完成させました。）
最終定理が偉大過ぎるので相対的に小定理なんて呼ばれています。
しかし、小なんて言葉で謙遜するにはあまりに素晴らしすぎる、美しすぎる定理とは思いませんか？
$a, a^2, a^3, \cdots$
という数列は、$p$を法として眺めると$p-1$周期でグルグル回ってるって主張しているんですよ！
神秘性を感じずにはいられません。
フェルマーの小定理の証明
それでは、フェルマーの小定理を証明していきましょう。
（フェルマーの小定理）
$p$が素数で、$a$が$p$の倍数ではない整数のとき、
$a^{p-1} \equiv 1(\mod p)$
が成り立つ
～脳内会議～
証明しよう！といっても、何から手を付けるべきか見えにくいと思います。
注目すべきポイントとしては、まず、
何についての定理を証明しようとしているか、という点です。
今回は、フェルマーの小定理を$a$についての定理と捉えるか、$p$についての証明と捉えるか
が重要です。
今回は整数$a$についての定理を証明している、と捉えることにしましょう
（これは好みの問題です。$a$に着目した方が観察結果を一般化している感が出るので、僕はこちらが気に入っていますが、$p$に着目してもに解けます）
次に着目すべきポイントは、条件です。
細かく分割すると、以下３つが条件として挙げられます。
・$p$は素数
・$a$は整数
・$a$は$p$の倍数ではない
あとはこれらを処理していくだけです。
まず、今回は整数$a$についての証明問題です。
この時点で、数学的帰納法が頭をよぎります。
整数問題（自然数も）＋証明＝数学的帰納法
は定石といってよいでしょう。
しかし数学的帰納法は自然数について発動する手法なので、
整数について発動する場合は正の数の場合と負の数の場合で場合分けが必要となります。
また、帰納法でアプローチする場合は、いきなり
$a^{p-1}\equiv 1(\mod p)$
を示すのは微妙に難しいので、両辺に$a$をかけた
$a^p \equiv a (\mod p)$
を示すと覚えておいてください。
ではいってみましょう！
（フェルマーの小定理）
$p$が素数で、$a$が$p$の倍数ではない整数のとき、
$a^{p-1} \equiv 1(\mod p)$
が成り立つ。
（証明）
まずは$a>0$の場合に
$a^p \equiv a (\mod p)$
が成り立つことを数学的帰納法によって示す。
$i)$ $a=1$の場合を考える。
$1^{p-1}=1\equiv 1 (\mod p)$
よって、$a=1$の場合は$a^p \equiv a (\mod p)$は成立$\cdots$①
$ii)$ $a=k$のとき、$k^p \equiv k(\mod p)$が成り立つと仮定する。
このとき、$a=k+1$で$(k+1)^{p} \equiv k+1 (\mod p)$が成り立つことを示す。
$(k+1)^p$について、二項定理より、
$(k+1)^p={}_p\mathrm{C}_0k^p+{}_p\mathrm{C}_1k^{p-1}・1+{}_p\mathrm{C}_2k^{p-2}・1^2+\cdots +{}_p\mathrm{C}_p1^p$
ここで、二項係数${}_p\mathrm{C}_m$ $1≦m≦p-1$を考える。
${}_p\mathrm{C}_m=\dfrac{p!}{m!(p-m)!}$←定義
${}_p\mathrm{C}_m$は自然数であるので、$\dfrac{p!}{m!(p-m)!}$も自然数である。
いま、$1≦m≦p-1$かつ$1≦p-m≦p-1$である。
$p$は素数であるので、$1$と自身以外に約数を持たない。
ゆえに、$p$と$m!(p-m)!$は互いに素である。
$\dfrac{p!}{m!(p-m)!}=p×\dfrac{(p-1)!}{m!(p-m)!}$
は自然数でなければならないので、
$\dfrac{(p-1)!}{m!(p-m)!}$は分子・分母で約分されて自然数にならなければならない。
そこで、
$\dfrac{(p-1)!}{m!(p-m)!}=s$ $s$は自然数と置くと、
$\dfrac{p!}{m!(p-m)!}=ps$となり、
${}_p\mathrm{C}_m=ps$であるため、
${}_p\mathrm{C}_m$は$p$の倍数となる。
ここで、
$(k+1)^p={}_p\mathrm{C}_0k^p+{}_p\mathrm{C}_1k^{p-1}・1+{}_p\mathrm{C}_2k^{p-2}・1^2+\cdots +{}_p\mathrm{C}_p1^p$
について、$p$を法として考えると、${}_p\mathrm{C}_m$が$p$の倍数であることから
$(k+1)^p \equiv ={}_p\mathrm{C}_0k^p+0+{}_p\mathrm{C}_p1^p (\mod p)$
となり、
$(k+1)^p \equiv k^p+1 (\mod p)$である。
仮定より、$k^p \equiv 1 (\mod p)$
であったので、
$k^p+1=k×k^{p-1}+1 \equiv k×1+1(\mod p)$
となり、
$(k+1)^p \equiv k+1 (\mod p)$
となる$\cdots$②
①と②より、数学的帰納法から、全ての正の整数$a$に関して、
$a^p \equiv a (\mod p)$
が成立する。
ここで、条件より、$a$は$p$の倍数ではない。
また、$p$は素数であるので、$a$と$p$は互いに素である。
ゆえに、
$a^p \equiv a (\mod p)$
の両辺を$a$で割ると、
$a^{p-1} \equiv 1 (\mod p)$
となる。
次に、$a<0$である場合を考える。
$a<0$より、
$-a>0$である。
ここで、$-a=b$と置く。
$b$は正の整数であるので、
$b^{p-1}\equiv 1(\mod p)$
が成り立つ。
$b=-a$であったので、
$(-a)^{p-1}\equiv 1 (\mod p)$
$(-1)^{p-1}(a)^{p-1} \equiv 1 (\mod p)$
が成り立つ。
ここで、
$p=2$の場合は$-1\equiv-1+2 \equiv 1(\mod 2)$
であり、
$p$が$2$より大きい素数の場合は
$(-1)^{p-1}=1$
であるので、
いずれにしろ
$a^{p-1}\equiv 1(\mod p)$
である。
したがって、
$p$の倍数でない$a$に対して
$a^{p-1}\equiv 1 (\mod p)$
が成り立つ
(証明終了)
まとめ
いかがでしたか？
今回は
$2, 2^2, 2^3 \cdots$
という等比数列を合同式を用いて観察することで
① ０が出るグループ
② 最後が１になるグループ
③ それ以外のグループ
の３つの分類をゲットし、
特に②のグループの観察を深めることで
フェルマーの小定理を得ました。
次回の記事では、③のグループについて深めていきたいと思います。
ご期待ください。
コメント