pepan フェルマー(Fermat)数 Fn=22n+1 が素数であるかどうかを判定する
int pepan(int n);
n フェルマー数における正整数
素数なら1、非素数(つまり、合成数)なら0、内部エラーが起きた ときは -1。
は素数であろうと予想した。この数は、n = 5, 6, 7, 8, ... に応じて 非常に速くとてつもなく大きくなる。したがってコンピュータなしの時代には、 これらの値を計算することはほとんど不可能であった。確かに、
F0 = 3 F1 = 5 F2 = 17 F3 = 257 F4 = 65537
は素数である。しかし、オイラー(1732年)により
F5 = 232+1 = 4294967297 = 641 x 6700417
は合成数であることが後にわかった。
本関数ではペパンの判定法を利用して、フェルマー数が素数であるかどうかを 調べる。ペパンの判定法によると、n が 1 以上のとき
3 (Fn-1) / 2 ≡ -1 (mod Fn)
の成り立つことが Fn が素数であるための必要十分条件である。
いまのコンピュータ時代では、多くの人たちの努力にもかかわらず、F4 より大きな素数は1つも見つかっていない。 なお、フェルマー数が合成数の場合、その素因数はすべて
k 2m+1 (m≧n+2)
の形をしている。
余談になるが、素数となるフェルマー数(フェルマー素数)を見つけることは なぜそんなに重要なのかというと、一つには、全く関係がなさそうな幾何学の 正多角形の作図問題と深い関係があることをガウスが発見したからである。
ガウスは、n の値が
・2 のベキである
・フェルマー素数である
・これらの2種類の数の積である
ときに、かつそのときにだけ、正 n 角形は定規とコンパスで作図可能である ことを証明した。 ガウスの墓石に刻まれた正17角形は、ちょうどフェルマー数 F2に 対応するものである。したがって作図可能な奇数正多角形はフェルマー素数より、
正3角形、5角形、15角形、17角形、51角形、85角形、...
などのみとなる。