§A4.7フェルマーの小定理とオイラーの定理

1 証明のスケッチ

$\{a, 2a, \dots, (p-1)a\}$という$p-1$個の数を、法$p$で見てみます。これは$\{1, 2, \dots, p-1\}$の並べ替えになっています。 理由は単射性です。もし$ia \equiv ja \pmod p$（$1\le i,j\le p-1$）なら$p \mid (i-j)a$。$p$は素数で$p \nmid a$だから$p \mid (i-j)$、範囲から$i=j$。$p-1$個の値が単射に$p-1$個の枠（$0$を除いた余り）へ収まるので全単射、つまり並べ替えです（どの$ia$も$0$にはなりません。$p \mid ia$なら$p\mid i$か$p \mid a$で、どちらも範囲外か仮定に反します）。

並べ替えなら、両方の積は法$p$で等しくなります。

$$a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod p \quad\Longrightarrow\quad (p-1)! \, a^{p-1} \equiv (p-1)! \pmod p$$

$(p-1)!$は$1$から$p-1$までの積で、どの因数も素数$p$で割り切れないから$\gcd((p-1)!, p) = 1$。だから両辺を$(p-1)!$で割ってよく（合同式の割り算ができる条件そのもの）、$a^{p-1} \equiv 1 \pmod p$が残ります。

2 オイラーの定理：法が素数でなくても

同じ議論は、法$n$が合成数でも通用します。$1$から$n$までのうち$n$と互いに素なもの全体（既約剰余系、個数は$\varphi(n)$）に$a$（$\gcd(a,n)=1$）を掛けても、同じ単射性の議論で既約剰余系の並べ替えになります。全部の積を比べれば、フェルマーの証明とそっくりの手順で

$$a^{\varphi(n)} \equiv 1 \pmod n$$

が出ます。オイラーの定理です。フェルマーの小定理は$n = p$（素数なら$\varphi(p) = p-1$）の特別な場合になっています。

3 使ってみる：$3^{100} \bmod 7$

$p=7$なので$3^6 \equiv 1 \pmod 7$（フェルマー）。$100 = 6 \times 16 + 4$なので

$$3^{100} \equiv (3^6)^{16} \cdot 3^4 \equiv 3^4 \pmod 7$$

$3^1\equiv3, 3^2\equiv2, 3^3\equiv6, 3^4\equiv 4 \pmod 7$より、$3^{100} \equiv 4 \pmod 7$。指数がどれだけ巨大でも、法より1小さい数で指数を割った余りだけ見ればよい、というのが定理の実用的な使い方です。

4 逆は成り立たない：擬素数

フェルマーの小定理の逆は成り立ちません。つまり$a^{n-1}\equiv1\pmod n$が成り立つからといって$n$が素数とは限りません。有名な例が$2^{340}\equiv1 \pmod{341}$で、$341 = 11 \times 31$は合成数です（$2$を底とする擬素数）。さらに悪いことに、$561 = 3\times11\times17$のようなカーマイケル数は、自分と互いに素などんな底$a$に対しても$a^{560}\equiv1\pmod{561}$を満たしてしまい、フェルマーテストを完全に欺きます。それでも「$a^{n-1}\not\equiv1 \pmod n$が1つでも見つかれば$n$は合成数と確定できる」という片方向の判定力は失われないため、フェルマーテストは今日の確率的素数判定法（さらに強力なミラー–ラビン法など）の出発点になっています。