Euler's Eyes
2026-10-11
フェルマーの小定理：べきと余り
数 2 をどんどん大きなべきにしていきましょう。それぞれを 7 で割って、余りを書きとめます。
| べき | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ |
|---|---|---|---|---|---|---|
| 値 | 2 | 4 | 8 | 16 | 32 | 64 |
| 7 で割った余り | 2 | 4 | 1 | 2 | 4 | 1 |
$2^6$ で余りは 1 になります。今度は 3 と素数 5 で試しましょう。$3^4=81$ は 5 で割ると 1 余ります。10 と素数 13 では、$10^{12}=1\,000\,000\,000\,000$ も 13 で割ると 1 余ります。
偶然でしょうか？ いいえ。これがフェルマーの小定理です。
定理の内容
$p$ が素数で、$a$ が $p$ の倍数でない整数なら、$a^{p-1}$ を $p$ で割った余りは 1 である。1801 年にガウスが作った合同式の記号では、
$$a^{p-1}\equiv1\pmod p.$$「小」という名前は、最終定理と区別するためだけのものです。実際には、小定理のほうがずっと役に立ちます。
証明のない手紙
フェルマーはこの定理を、1640 年 10 月 18 日、数学者ベルナール・フレニクル・ド・ベシーへの手紙で伝えました。いつものように、証明は示しませんでした。
長すぎるのを恐れなければ、証明をお送りするところです。
— フェルマー、フレニクル・ド・ベシーへの手紙（1640）
最初に発表された証明は、ほぼ 100 年後、1736 年のレオンハルト・オイラーによるものです。後に、ライプニッツも 1683 年ごろに証明をもっていて、発表しなかったことがわかりました。
「シャッフル」による証明
$p=7$、$a=3$ の場合に定理を証明しましょう。一般の場合も議論はまったく同じです。
$1,2,3,4,5,6$ を書きます。それぞれに 3 を掛け、7 で割った余りをとります。
$$3,\ 6,\ 9\to2,\ 12\to5,\ 15\to1,\ 18\to4.$$余りは $3,6,2,5,1,4$。もとの数が、順番を入れ替えて並んでいるだけです。これはいつでも起こります。余りが 0 になることはありません。$p$ は $a$ も $k$ も割り切らないからです。同じ余りが二度出ることもありません。もし $ai$ と $aj$ の余りが同じなら、$p$ は $a(i-j)$ を、したがって $i-j$ を割り切りますが、1 から $p-1$ までの異なる二つの数ではそれは不可能だからです。
二つの組が同じなので、その積の余りも同じです。
$$(3\cdot1)(3\cdot2)\cdots(3\cdot6)\equiv1\cdot2\cdots6\pmod7,$$つまり $3^6\cdot6!\equiv6!\pmod7$。7 は素数で $6!$ を割り切らないので、$6!$ を約して $3^6\equiv1\pmod7$ が得られます。確かめると $3^6=729=7\cdot104+1$。
巨大な計算を楽に
$3^{100}$ を 7 で割った余りは？ 定理がなければ 48 桁の数を計算しなければなりません。定理があれば、$3^6\equiv1$ で $100=6\cdot16+4$ なので、
$$3^{100}=\left(3^6\right)^{16}\cdot3^4\equiv1^{16}\cdot81\equiv4\pmod7.$$巨大なべきを小さくするこの力は、インターネットでの買い物やパスワードを守る RSA 暗号の基礎になっています。RSA はオイラーによるこの定理の一般化を使っていて、それはオイラーのシリーズで紹介しています。
逆には注意
$p$ が素数なら $a^{p-1}\equiv1$。しかし逆は成り立ちません。素数でないのにテストに合格する数があるのです。もっとも小さな「くせ者」は $561=3\cdot11\cdot17$ で、561 と共通の因数をもたないすべての $a$ について $a^{560}\equiv1\pmod{561}$ を満たします。このような数をカーマイケル数といいます。だからこの定理は、ある数が素数でないことは示せても、それだけで素数であることは示せないのです。
練習：3¹⁰ を 11 で割った余りは？
11 は素数で 3 を割り切らないので、$3^{10}\equiv1\pmod{11}$。余りは 1。確かめると $3^{10}=59\,049=11\cdot5368+1$。
練習：2¹⁰⁰ を 13 で割った余りは？
$2^{12}\equiv1\pmod{13}$ で、$100=12\cdot8+4$。したがって $2^{100}\equiv2^4=16\equiv3\pmod{13}$。余りは 3。
資料： フェルマーの伝記、MacTutor。