(55) 素数の正則性チェック(要加筆)

Fermatの最終定理が証明されるまでの歴史のなかで、Kummerが正則素数に限定したものを証明したそうです。正則素数pは、Bernoulli数の偶数項の分子のいずれも割り切らない素数という性質と同値であることがKummerによって示されたそうです。

では、素数の正則性を具体的に見ていきます。
最初の例として、p=7の場合を見てみましょう。

/* 9.2.5m */
print(bern(2),", ", bern(4))$

どちらも分子は1なので、7は正則素数です。

次にp=37の場合を見てみましょう。

/* 9.2.7m */
print(bern(32))$
mod(num(%), 37);

37は非正則素数だとわかりました。

天下り的にの分子が37で割り切れることを見ましたが、スクリプトを書けば全数チェックも容易にできます。ここでは少し凝って、Bernoulli数の母函数を使って全数チェックしてみます。

左辺をMaclaurin展開することで、係数にBernoulli数が現れます。(p-1)!を掛けると、係数が整数係数となるそうです。(n!は清算できますが、Bernoulli数の分母が清算できる理由がわからない。)
(p-1)!はpで割れませんから、整数係数がpで割り切れないことと正則素数であることは同値です。さて、Maximaで一気に確認してましょう。

/* 9.2.10m */
p : 37$
s : taylor((p - 1)!*t/(%e^t - 1), t, 0, p - 3);
maplist(lambda([x], mod(at(x, t = 1), p)), s);

割り切れた係数があるので、37は非正則素数です。

参考文献

1. Crandall, Mathematica―理工系ツールとしての (アジソン ウェスレイ・トッパン情報科学シリーズ) p.268-p.272
2. ウィキペディア, 正則素数