フェルマーの小定理

フェルマーの小定理は、素数に関する整数論の基本的な定理です。大きなべき乗の余りを求める問題で威力を発揮し、暗号理論の基礎にもなっています。

定理の内容

$p$ を素数、 $a$ を $p$ の倍数でない整数とするとき

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

が成り立ちます。これがフェルマーの小定理です。

別の形

両辺に $a$ をかけると $a^{p} \equiv a (mod p)$ となります。こちらの形は $a$ が $p$ の倍数でも成り立ちます。

小定理という名前

「小」がつくのは、フェルマーの最終定理（大定理）と区別するためです。

$p = 7$ 、 $a = 3$ のとき、定理より $3^{6} \equiv 1 (mod 7)$ が成り立つはずです。

実際に計算してみましょう。

$3^{1} = 3$

$3^{2} = 9 \equiv 2 (mod 7)$

$3^{3} = 27 \equiv 6 (mod 7)$

$3^{4} = 81 \equiv 4 (mod 7)$

$3^{5} = 243 \equiv 5 (mod 7)$

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

確かに $3^{6} \equiv 1 (mod 7)$ が成り立っています。

$2^{100}$ を 13 で割った余りを求めます。

13 は素数で、2 は 13 の倍数でないので、フェルマーの小定理より

$2^{12} \equiv 1 (mod 13)$

$100 = 12 \times 8 + 4$ なので

$2^{100} = 2^{12 \times 8 + 4} = (2^{12})^{8} \times 2^{4} \equiv 1^{8} \times 16 \equiv 16 \equiv 3 (mod 13)$

よって、余りは 3 です。

指数を $p - 1$ で割った余りを求める

$a^{p - 1} \equiv 1$ を利用して式を簡単にする

残りの小さなべき乗を計算する

$a, 2 a, 3 a, \dots, (p - 1) a$ を $p$ で割った余りを考えます。これらはすべて異なり、 $1, 2, 3, \dots, p - 1$ の並べ替えになっています。

したがって

$a \cdot 2 a \cdot 3 a \dots (p - 1) a \equiv 1 \cdot 2 \cdot 3 \dots (p - 1) (mod p)$

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

$(p - 1)!$ は $p$ と互いに素なので、両辺から消去できて

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

が得られます。

素数でないと使えない

$p$ が合成数の場合、フェルマーの小定理は成り立ちません。合成数に対してはオイラーの定理を使います。

a

が

p

の倍数だと使えない

$a$ が $p$ の倍数のとき、 $a \equiv 0 (mod p)$ なので $a^{p - 1} \equiv 0 (mod p)$ となり、1 にはなりません。

フェルマーの小定理は、RSA 暗号などの公開鍵暗号の理論的基盤にもなっている重要な定理です。