📂整数論

カーマイケル数

定義 ¹

整数 $n$ が全ての $1 \le a \le n$ に対して $a^{n} \equiv a \pmod{n}$ を満たす場合、カーマイケル数と呼ばれる。

定理

全てのカーマイケル数は$2$ を除く異なる素数の積で表される。

説明

カーマイケル数は合成数でありながらフェルマーの小定理を通過する、つまり素数のように見える数だ。例えば、$561=3 \cdot 11 \cdot 17$ は合成数だが$a^{561} \equiv a \pmod{561}$ は常に成り立つ。

これらのカーマイケル数を捕まえるためにミラー-ラビン素数判定法がある。

証明

$n$ をカーマイケル数とする。

パート1。 $a = n-1$ とすると $n-1 \equiv -1 \pmod{n}$ であるため $$(n-1)^{n} \equiv (-1)^{n} \equiv -1 \pmod{n}$$ 上記の合同式が成り立つのは$n$ が奇数のときだけである。

パート2。 $n$ が$2$ を除く素数 $p_{1}, \cdots , p_{m}$ に対して$n = p_{1}^{r_{1} + 1} \cdots p_{m}^{r_{m} + 1}$ と表されるとする。ここで $\displaystyle r : = \max \left\{ r_{1}, \cdots , r_{m} \right\}$ と置き$r=0$ であることを示せば証明は完了である。この$r$ に対応する素数を$p$ とする。

$n$ はカーマイケル数であるので$p^{rn} \equiv p^{r} \pmod{n}$ が成り立ち、$n$ は$\left( p^{rn} - p^{r} \right)$ を割る必要がある。また、$n$ の約数の中には$p^{r+1}$ もあるため、$p^{r+1}$ は$\left( p^{rn} - p^{r} \right)$ を割る必要がある。つまり $${{ p^{rn} - p^{r} } \over { p^{r+1} }} = {{ p^{rn - r} - 1 } \over { p }}$$ これは整数であることを意味し、これが可能なのは分子が$0$ となる$r=0$ のみである。

■