フェルマーの小定理

この証明の道すじ。 余りを7時間の時計で読み、素数と合成数で余りを表にする。$3\times 1$から$3\times 6$までの余りが1〜6の並べ替えになることから公式を導き（図で納得する）、オイラーの二項展開の道でも導く（式で確かめる）。最後に、初めて1に戻る回数が$p-1$の約数になることを示す。

式の文字を読む

$a$は何回も掛ける整数、$p$は割る数で、素数である。$p\nmid a$は「$a$は$p$で割り切れない」と読む。$a^{p-1}$は$a$を$p-1$回掛けた数で、どの文字にも単位は無い。

$\equiv$（合同）は、割った余りが等しいことを表す。7時間で一回りする時計で、0時から10時間進めると、針は1周して3を指す。10を7で割った余りは3なので、次のように書く。

$$10\equiv 3(\mathrm{mod}7)$$

「7を法として、10と3は合同」と読む。法は、割る数の7のことだ。17時間進めても針は2周して3を指すので、$17\equiv 3$で、$17\equiv 10$とも書ける。

余りが等しい数どうしを掛けると、積の余りも等しい。$9\equiv 2$と$12\equiv 5$なら、$9\times 12=108$も$2\times 5=10$も、7で割って3余る。$9=7+2$と$12=7+5$を掛けて広げると、7の倍数でない項は$2\times 5$しか残らないからだ。

素数と合成数で試す

5と7で割る場合を、$a=2$と$a=3$で試す。$a$を1回、2回と掛けるたびに割った余りを書くと、$p-1$回目はどれも1になる。

割る数	掛ける数	1回目から順に、割った余り
5	2	2, 4, 3, 1
5	3	3, 4, 2, 1
7	2	2, 4, 1, 2, 4, 1
7	3	3, 2, 6, 4, 5, 1

7と2の行は、3回目ですでに1に戻り、そこから同じ並びのくり返し。早く戻っても、6回目には必ず1にいる。

では、合成数で割るとどうなるか。6で割る場合、5回掛けた数の余りは次のとおりで、1になるのは$a=1$だけだ。

$a$	1	2	3	4	5
$a^5$を6で割った余り	1	2	3	4	5

図で納得する

なぜ素数なら1に戻るのか。$p=7$、$a=3$で、3に1から6までを掛けた6つの数を、7で割ってみる。

$$\begin{array}{rl}3\times 1& =3\equiv 3\\ 3\times 2& =6\equiv 6\\ 3\times 3& =9\equiv 2\\ 3\times 4& =12\equiv 5\\ 3\times 5& =15\equiv 1\\ 3\times 6& =18\equiv 4\end{array}$$

余りの3, 6, 2, 5, 1, 4は、1から6までを、ちょうど1回ずつ並べ替えたものだ。7で割る限り、$a$を2や6に替えても余りは1〜6の並べ替えになる。6で割って$a=2$とすると、余りは2, 4, 0, 2, 4と重なり、1と3と5が抜ける。

$3\times 1$から$3\times 6$までを全部掛けた積と、余りの3, 6, 2, 5, 1, 4を全部掛けた積は、余りが等しい数どうしを掛けたものなので、7で割った余りも等しい。前の積は3を6個くくり出すと$3^6\times (1\times 2\times \cdots \times 6)$で、あとの積は1〜6を並べ替えて掛けただけなので、どちらにも$1\times 2\times \cdots \times 6=720$が入る。

$$3^6\times 720\equiv 720(\mathrm{mod}7)$$

両辺の差$(3^6-1)\times 720$は、7の倍数だ。7は素数なので、2つの数の積を割り切るなら、どちらかを割り切る。$720=7\times 102+6$は7で割り切れないから、7は$3^6-1$を割り切る。

$$3^6\equiv 1(\mathrm{mod}7)$$

一般の素数$p$でも、同じ2つの手順を踏めばよい。$a\times 1$から$a\times (p-1)$までの余りは、どれも0でなく、互いに違うので、1〜$p-1$の並べ替えになる。全部掛けると、次の式が出る。

$$a^{p-1}\times (p-1)!\equiv (p-1)!(\mathrm{mod}p)$$

$(p-1)!$は「$p-1$の階乗」と読み、$p-1$から1まで全部掛けた数で、$6!=720$である。1〜$p-1$のどれも素数$p$で割り切れないので、積の$(p-1)!$も$p$で割り切れない。

7のときと同じく、両辺の差$(a^{p-1}-1)\times (p-1)!$は$p$の倍数だ。だから$p$は$a^{p-1}-1$を割り切り、両辺から$(p-1)!$を外した$a^{p-1}\equiv 1(\mathrm{mod}p)$が出る。

余りがどれも違うのは、2つが等しいと差の$a\times (r-s)$が$p$の倍数になるのに、$a$も$r-s$も$p$で割り切れないからだ。$r$と$s$は1〜$p-1$の違う数なので、$r-s$は0でなく、大きさも$p$より小さい。余りが0にならないのも、$a$も$k$も$p$で割り切れないからである。

$p$が素数で、$a$を割り切らないことが効くのは、この2か所だ。$a$が$p$の倍数、たとえば$a=7$なら、$7\times k$の余りはどれも0で、並べ替えにならない。

合成数の10で$a=3$とすると、余りは3, 6, 9, 2, 5, 8, 1, 4, 7と並べ替えにはなる。ところが$9!=362880$が10で割り切れるので両辺から外せず、$3^9$を10で割った余りは3のままだ。

式で確かめる

オイラーが1736年にたどったのは、二項展開の道だった。$a$がどんな整数でも成り立つ$a^p\equiv a$を先に示し、そのあとで両辺を$a$で割る。

1. 二項定理で$(a+1{)}^p$を展開する

   $$\begin{array}{rl}& (a+1{)}^p\\ & =a^p+{}_p{\mathrm{C}}_1{a}^{p-1}+\cdots \\ & +{}_p{\mathrm{C}}_{p-1}a+1\end{array}$$

2. 両端の$a^p$と1を左辺へ移す

   $$\begin{array}{rl}& (a+1{)}^p-a^p-1\\ & ={}_p{\mathrm{C}}_1{a}^{p-1}+\cdots +{}_p{\mathrm{C}}_{p-1}a\end{array}$$

${}_p{\mathrm{C}}_k$は、$p$個から$k$個を選ぶ選び方の数である。$p$が素数なら、$k$が1から$p-1$のとき、${}_p{\mathrm{C}}_k$はどれも$p$で割り切れる。分子の$p\times (p-1)\times \cdots$には$p$があり、分母の$k\times \cdots \times 1$には$p$より小さい数しかないので、$p$が約分で消えずに残るからだ。

たとえば${}_7{\mathrm{C}}_3=(7\times 6\times 5)÷(3\times 2\times 1)=35=7\times 5$で、7が残る。パスカルの三角形の7段目に並ぶ7, 21, 35, 35, 21, 7がどれも7で割り切れることは、二項定理の例題5でも計算できる。

3. 右辺の係数はすべて$p$の倍数なので、右辺も$p$の倍数

   $$\begin{array}{rl}& (a+1{)}^p-a^p-1\\ & \equiv 0(\mathrm{mod}p)\end{array}$$

4. 両辺に$a^p-a$を足し、$a+1$の式に組みかえる

   $$\begin{array}{rl}& (a+1{)}^p-(a+1)\\ & \equiv a^p-a(\mathrm{mod}p)\end{array}$$

手順4は、$a^p-a$が$p$の倍数なら、1つ上の$(a+1{)}^p-(a+1)$も$p$の倍数だと言っている。1段目の$1^p-1=0$は$p$の倍数なので、そこから1段ずつ上がれば、どの段も$p$の倍数のままだ。こうして1段ずつ示していく証明を、数学的帰納法という。

5. $1^p-1=0$から始め、手順4で$a$を1つずつ上げる

   $$a^p\equiv a(\mathrm{mod}p)$$

6. $p$で割り切れない$a$なら、両辺を$a$で割れる

   $$a^{p-1}\equiv 1(\mathrm{mod}p)$$

手順5は、$a$が$p$の倍数でも成り立つ形だ。負の$a$も、$p$の倍数を足して正にすれば余りは変わらない。手順6では、$a^p-a=a\times (a^{p-1}-1)$が$p$の倍数で、$p$は$a$を割り切らないので、$a^{p-1}-1$を割り切る。

初めて1に戻る回数

フェルマーが手紙に書いたのは、もう少し強い形だった。3の累乗を13で割ると3, 9, 1と進み、3回目に1に戻って、そこから同じ3つをくり返す。

初めて1に戻る回数を$d$とすると、余りは$d$回ごとに同じ並びをくり返す。$m$回目に1にいるとき、$m$を$d$で割って商を$q$、余りを$r$とすると、$m=d\times q+r$なので、次のように書ける。

$$a^m=(a^d{)}^q\times a^r\equiv a^r(\mathrm{mod}p)$$

左辺は1と合同なので、$a^r\equiv 1$だ。$r$は0以上$d$未満で、1回目から$d-1$回目までは1に戻らないから、$r=0$しかない。1になる回数はどれも$d$の倍数で、公式の$m=p-1$も$d$の倍数、つまり$d$は$p-1$の約数である。7で割って2を掛けたときの3回も、6の約数だった。