かの有名なフェルマー(1665年)は、つぎのフェルマー数 Fn
    Fn = 22n + 1 (n = 0, 1, 2, ...)

は素数であろうと予想した。この数は、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)

の形をしている。

<関数名>
  pepan フェルマー(Fermat)数 Fn=22n+1 が素数であるかどうかを判定する

<形式>
  int pepan(int n);

<引数>
  n フェルマー数における正整数

<関数値>
  素数なら 1、非素数(つまり、合成数)なら0、内部エラーが起きたときは -1。

用例
  pepan(3);

<関数本体>
  pepan.c

素数となるフェルマー数(フェルマー素数)を見つけることはなぜそんなに重要なのかというと、一つには、全く関係がなさそうな幾何学の正多角形の作図問題と深い関係があることをガウスが発見したからである。

ガウスは、n の値が

    ・2 のベキである
    ・フェルマー素数である
    ・これらの2種類の数の積である

ときに、かつそのときにだけ、正 n 角形は定規とコンパスで作図可能であることを証明した。ガウスの墓石に刻まれた正17角形は、ちょうどフェルマー数 F2に対応するものである。したがって作図可能な奇数正多角形はフェルマー素数より、

    正3角形、5角形、15角形、17角形、51角形、85角形、...

などのみとなる。

Comments are closed.

Post Navigation