サラリーマンのすらすらＩＴ日記

厄介なのは、フェルマーの小定理の逆が一般に成り立たないこと。つまりnが素数でなくてもこの合同式が成り立つことがあります。例えば、91は素数ではありませんが（=7×13）、

3⁹⁰ ≡ 1 mod 91

となるから。もっとも

2⁹⁰ ≡ 64 mod 91

なので、素数でないことがわかります（91くらいの小さい数なら、上記の合同式の計算の方が大変だが）。

さらに厄介なのが、nが素数でないにもかかわらず、nと互いに素なすべてのaに対して、a^n-1 ≡ 1 mod nが成り立つケースがあること。これではこの素数判定法は使えません。このような整数をカーマイケル数といいます。カーマイケル数は無数に存在することがわかっており、小さいものから列挙すると561,1105,1729,2465,...となります。

ここで気が付くのが「1729」。タクシーと2つの3乗数の和で紹介した1729です。1729は2つの整数の3乗数の和として2通りに表すことができる最小の数であると同時に、カーマイケル数でもあるわけです。これは面白い。