Wieferich素数のこと

I. Valdi, Mathematica 計算の愉しみを見ていて，Wieferich素数を思い出した．この本は面白い本だが（かなり誤植が多いが）残念ながら絶版の模様．Mathematica版のハッカーのたのしみ―本物のプログラマはいかにして問題を解くかみたいな感じである．

素数pがWieferich素数とは，2^(p-1)はp^2で割り切れるとき（2016/03/29訂正：$(2^{p-1}-1$が$p^2$で割り切れること）を言う（^は冪乗の記号．2^2=4, 2^3=8, ...）．Fermatの小定理によって，2^(p-1)は（同：$2^{p-1}-1$は）常にpで割り切れる．これは非常に稀な素数のように思われ，現在までにp=1093, 3511以外には見つかっていない．

Crandall, Dilcher and Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66, 1997によると，4×10^12までで上の2つしか見つかっていない（全文がPDFで読める）．またJ. Knauer and J. Richstein, The continuing search for Wieferich primes, Math. Comp. 74, 2005だと，やはり1.25×10^15まで探しても上の2つしか見つからないらしい．Knauer and Richsteinの論文では，インターネットを用いた分散計算を導入して記録を伸ばしている．

2^(p-1) = 1 + ap (mod p^2)と書いたとときにaが0からp-1でランダムだと仮定すると，pがWieferich素数，つまりa = 0となる確率が計算できる．x以上y以下ののWieferich素数の個数はΣ1/p ～ log(log(y)/log(x))であり，10^15まで行っても見つからないのは無理もないのかもしれない（これもCrandallらの論文にある）．

探索は，基本的にはbrute force（力ずく）で，素数を生成し，上の合同式をチェックする．常にp^2で割った剰余のみ計算すればよいし，その他いろいろなテクニックを使う（上記Crandall, Dilcher, Pomerance参照）．

この項続く，かも;-)