フェルマーの小定理の逆が成り立たない例

フェルマーの小定理は $(a,\ p) = 1$ なる整数 $a$ と素数 $p$ に対して $p - 1\mid n\ (n \in \mathbb{N})$ ならば

$$a^n \equiv 1 \pmod{p}$$

が成り立つという定理。この逆の、$n\in \mathbb{N}$ に対して $a^{n} \equiv 1 \pmod{p}$ ならば $p - 1\mid n$ である、という主張は成り立たない。

• 例

$$2^{60} \equiv 1 \pmod{151}$$

$p - 1$ 法とフェルマーの小定理

$p - 1$ 法は $n\in \mathbb{N}$ の非自明な約数を探索するために次のような計算をする:

$$\gcd(a^k - 1,\ n)$$

ここで $a,\ k\in \mathbb{N}$ である。これがうまくいく理由は、もし $p - 1\mid k$ ならばフェルマーの小定理により

$$a^k\equiv 1 \pmod{p}$$

が成り立つ。さらにもし $p\mid n$ ならば $p\mid \gcd(a^k - 1,\ n)$ となる。よって $\textrm{mod}$ の計算（繰り返し二乗法）と最大公約数の計算（ユークリッドの互除法）で $n$ の約数を取り出すことができる。

この方法が優れている点は、$n$ の素因数によっては計算量が少なくなるため高速であることである。しかし $p - 1$ が小さな素因数たちから成る smooth number でない場合、試し割り法より遅い場合もある。

$p - 1$ 法の例

$n = 49981 = 151 \times 331$ に対して $p - 1$ 法を適用する。$\gcd(2^k - 1, 49981)$ を $k = 1,\ 2,\ \cdots,\$ とすると、$k\le 14$ では $\gcd(2^k - 1, 49981) = 1$ であり $k = 15$ で初めて 非自明な約数を得る:

$$\gcd(2^{15} - 1, 49981) = 151$$

この例では $p - 1\mid k$ すなわち $151 - 1\mid 15$ は成り立たない。だがなぜ非自明な約数が見つかったのだろう。

$(\mathbb{Z}/151\mathbb{Z})^\times$ の原始根の一つは $6$ である。これは

>>> pow(6, 75, 151)
150

となることからわかる。$a = 6$ で $p - 1$ 法を行うと

$$\gcd(6^{150} - 1, 49981) = 151$$

より $p - 1\mid k$ となっている。$6^x \equiv 2 \pmod{151}$ となる $x$ は次のようにしてわかる:

>>> next((n, pow(6, n, 151)) for n in range(1, 151) if pow(6, n, 151) == 2)
(70, 2)

よって $x = 70$ である。そこで次のような計算をしてみると

>>> gcd(6 ** 1050 - 1, 49981)
151

となり、$k = 1050$ でも非自明な約数を得ることができた:

$$\gcd(6^{1050} - 1, 49981) = 151$$

今日はここまで。