漫画 はじめアルゴリズム 2巻 #8 大きな差

三原和人　2017年　講談社

フェルマーの小定理

小学5年生の関口ハジメが天才的な数学の才能を持つことを，老数学者の内田豊に見いだされ，成長していくという話です．やはり数学の得意な手嶋ナナオと加茂川で知り合う場面です．今回登場したフェルマーの小定理の証明はいくつか知られていますが，ここでは2種類の証明が出てきました．

[フェルマーの小定理] 整数$a$と素数$p$が互いに素であるとき，次式が成りたつ． $$a \ ^{p-1} \equiv 1  \pmod p$$

言い換えると「整数$a$が素数$p$の倍数でないとき，$a \ ^{p-1}$を$p$で割った余りは1になる」という定理です．

[手嶋ナナオの証明] $$\bar{ a } \in \left( \mathbb{ Z }/ p \mathbb{ Z } \right ) ^ {\times}とすると$$ $$|\left( \mathbb{ Z }/ p \mathbb{ Z } \right ) ^ {\times}|=p-1$$ $$\left( \mathbb{ Z }/ p \mathbb{ Z } \right ) ^ {\times}は有限巡回群なので$$ $$ラグランジュの定理より$$ $$\bar{ a }\ ^{p-1}\equiv \bar{ 1 }  \pmod p$$

[関口ハジメの感想]

これ　テジマの式　……  

すごい

きれい…  

[関口ハジメの証明] $$(\ \underbrace{1+1+\cdot\cdot\cdot\cdot+1\ }_{aコ})^p \equiv 1^p+1^p+\cdot\cdot\cdot\cdot+1^p$$ $$\quad\ \equiv a$$ $$∴ \quad a ^p \equiv a  \pmod p$$ $$(a,p)=1\ なので$$ $$a ^{p-1}\equiv 1  \pmod p$$

[手嶋ナナオの感想]

二項定理…？　

二項係数が割り切れる事実を使ったのか…？　

こんな幼稚な方法でも解けるのか…

[手嶋ナナオの証明] は群論を使っています．群とは，演算が閉じていて（例えば有理数×有理数＝有理数となるので有理数は掛け算について閉じている），結合法則 $a(bc)=(ab)c$ が成りたち，単位元（有理数なら1）と逆元（有理数 $a$ には逆数 $\frac{1}{a}$ ）が存在する集合をいいます．

まず$\mathbb{ Z }/ p \mathbb{ Z }$は，$p$で割った余りが等しい数で類別される集合の集合を表します． $$\mathbb{ Z }/ p \mathbb{ Z }=\{\bar{ 0 }, \bar{ 1 }, \bar{ 2 }, \cdot\cdot\cdot\cdot\overline{ p-1 }\}$$

（例えば$\overline{ 2 }$は$p$で割った余りが2になる数の集合）

そこから$\bar{ 0 }$（$p$の倍数の集合）を除いたものが$\left( \mathbb{ Z }/ p \mathbb{ Z } \right ) ^ {\times}$です．（証明の1行目） $$\left( \mathbb{ Z }/ p \mathbb{ Z } \right ) ^ {\times}=\{\bar{ 1 }, \bar{ 2 }, \bar{ 3 }, \cdot\cdot\cdot\cdot\overline{ p-1 }\}$$ その位数（集合の個数）$|\left( \mathbb{ Z }/ p \mathbb{ Z } \right ) ^ {\times}|$ は $p-1$（個）になります．（証明の2行目）

具体例として$\mathbb{ Z }/ p \mathbb{ Z }$を$p=7$で考えましょう．これは小学4年生で習うカレンダー算（日暦算）をイメージすると分かりやすいです．整数全体を曜日が同じ日で類別します．例えば7で割って2余る数の集まり$\{…, 2, 9, 16, 23, 30, …\}$を$\overline{ 2 }$と表すと，$\mathbb{ Z }/7\mathbb{ Z }=\{\overline{ 0 },\overline{ 1 },\overline{ 2 },\overline{ 3 },\overline{ 4 },\overline{ 5 },\overline{ 6 }\}$となります．　

そこから$\bar{ 0 }$（$7$の倍数の集合）を除いた$(\mathbb{ Z }/7\mathbb{ Z })^{\times}=\{\overline{ 1 },\overline{ 2 },\overline{ 3 },\overline{ 4 },\overline{ 5 },\overline{ 6 }\}$は有限巡回群（位数が有限で，単位元以外のあるひとつの元を累乗していくと他のすべての元を表すことができる群）なので， 「$(\mathbb{ Z }/p\mathbb{ Z })^{\times}$の元の位数（$\overline{ a }^n \equiv \overline{ 1 }$となる最小の$n$）が$p-1$の約数になる」というラグランジュの定理が使えることが分かります.（証明の3, 4行目）

実際，$\overline{ 1 }^1\equiv\overline{ 1 }, \  \overline{ 6 }^2\equiv\overline{ 1 }, \  \overline{ 2 }^3\equiv\overline{ 4 }^3\equiv\overline{ 1 }, \   \overline{ 3 }^6\equiv\overline{ 5 }^6\equiv\overline{ 1 }$となることから，$(\mathbb{ Z }/7\mathbb{ Z })^{\times}$の元の位数は1, 2, 3, 6，すなわち6の約数になっています．すると$(\mathbb{ Z }/7\mathbb{ Z })^{\times}$の元はどれも6乗すれば$\overline{ 1 }$になるので，$\overline{ a }^6\equiv \overline{ 1 } \pmod 7$が成り立ちます．これは7以外の素数$p$でも成り立ちますから次式が確かめられました． $$\overline{ a }^{p-1}\equiv \overline{ 1 } \pmod p$$

[関口ハジメの証明] は二項定理を一般化した多項定理を使っています．二項定理 $$(x+y)^p=\sum_{r=0}^{p} {}_p \mathrm{ C }_r x^{p-r} y^r$$ の展開式の係数は，${}_p \mathrm{ C }_0=1$と${}_p \mathrm{ C }_p=1$以外はpで割り切れますから，次式が成り立ちます． $$(x+y)^p \equiv x^p+y^p \pmod p$$ 同様に3つ以上の項の展開でも次式が成り立ちます． $$(x_1+x_2+\cdot\cdot\cdot+x_a)^p \equiv x_1^p+x_2^p+\cdot\cdot\cdot+x_a^p \pmod p$$ これに$x_i=1$を代入すると次式になります．（証明の1～3行目） $$(1+1+\cdot\cdot\cdot+1)^p \equiv 1^p+1^p+\cdot\cdot\cdot+1^p \pmod p$$ $$∴ \quad a ^p \equiv a  \pmod p$$ ここで，両辺を$a$で割って終わりかと思いますが，$=$ではなく$\equiv$なのでそれはできません．この式より，$a ^p-a$は$p$の倍数になります．すると，$a(a ^{p-1}-1)$が$p$の倍数となり，$(a,p)=1$（$a$と$p$は互いに素）より $a$は$p$の倍数ではないので，$a ^{p-1}-1$の方が$p$の倍数になります．よって，次式が成り立ちます． $$a ^{p-1}\equiv 1  \pmod p$$

証明が「すごい」とか「きれい」などの感想は良いと思いますが，この「幼稚」という感想は賛同できませんでした．

[参考]

フェルマーの小定理とその3通りの証明
https://mathlandscape.com/fermat-little/