フェルマー素数の原始根について

939

導入

よく知られているように、素数 $p$ がフェルマー素数の時、正 $p$ 角形は作図可能です。

現在知られているフェルマー素数は $3, 5, 17, 257, 65537$ の $5$ 個ですが、これらの $p$ について正 $p$ 角形の作図をしようとすると、 $p = 17$ くらいから $F_{p}$ の原始根を一つ固定して考えたくなる状況が発生します。

$p = 17$ の時には、原始根として $3$ が取れます。実際、 $3^{n} mod p$ は

$3^{1} \equiv 3, 3^{2} \equiv 9, 3^{3} \equiv 10, 3^{4} \equiv 13, 3^{5} \equiv 5, 3^{6} \equiv 15, 3^{7} \equiv 11, 3^{8} \equiv 16 \equiv - 1$
より $3^{16}$ で初めて $1$ と合同となり、原始根であることが比較的簡単に確認できます。

実は現在知られているその他のフェルマー素数でも $3$ が原始根であることが計算で確かめられます。それだけではなく、なんと次の事実が成り立ちます。

フェルマー素数の原始根

$p$ が $5$ 以上のフェルマー素数のとき、 $(Z / p Z)^{\times}$ の生成元（原始根）として常に $3$ が取れる。

常に、と書きましたが、現在知られている $5$ 以上のフェルマー素数は $5, 17, 257, 65537$ のたった $4$ 個です。

もしフェルマー素数がこれ以降無いことが証明されてしまうと、この定理は威力を発揮しないまま終わってしまう悲しい状態になってしまうのですが、もしなんらかの方法で新たなフェルマー素数が発見された時、原始根として計算するまでもなく $3$ が取れるのです！

（ただし後述するとおり、この逆に近い事実が成り立っており、これを用いてフェルマー数 $F_{n} = 2^{2^{n}} + 1$ が素数かどうかの判定を行うこともあるようです（Pépin's test））

ということでこの定理の証明を以下に行います。

証明

一般に素数 $p$ について、 $(Z / p Z)^{\times}$ の原始根が常に存在する。それを一つとって $g$ とする。任意の $a \in (Z / p Z)^{\times}$ に対して $a = g^{ν (a)}$ なる $ν (a)$ がmod $p - 1$ で一意に定まり、

$(\frac{a}{p}) = (- 1)^{ν (a)}$

と書ける。ここで $(\frac{a}{p})$ は平方剰余記号。

さて、 $g$ は原始根だから、 $g^{\frac{p - 1}{2}} \equiv - 1$ mod $p$ が成り立ち、

$(\frac{a}{p}) = (- 1)^{ν (a)} \equiv (g^{\frac{p - 1}{2}})^{ν (a)} = (g^{ν (a)})^{\frac{p - 1}{2}} = a^{\frac{p - 1}{2}} mod p$

が成り立つ（いわゆるEulerの規準）。

さて、 $3$ が原始根であることを言うには、 $3^{\frac{p - 1}{2}} \equiv - 1 mod p$ を言えば良いが、上記により

$(\frac{3}{p}) = - 1$

を言えば良いことになる。ここで平方剰余の相互法則が使えて

$(\frac{3}{p}) = (- 1)^{\frac{3 - 1}{2} \frac{p - 1}{2}} (\frac{p}{3}) = (- 1)^{\frac{p - 1}{2}} (\frac{p}{3})$

が成り立つが、今 $p = 2^{2^{n}} + 1 (n \geq 1)$ より $\frac{p - 1}{2} = 2^{2^{n} - 1}$ は偶数だから

$(\frac{3}{p}) = (\frac{p}{3})$

となる。また、 $p = 2^{2^{n}} + 1 \equiv (- 1)^{2^{n}} + 1 = 2 mod 3$ だから結局

$(\frac{3}{p}) = (\frac{2}{3}) = - 1$

となる。以上より

$3^{\frac{p - 1}{2}} \equiv - 1 mod p$ が言えた。よって $3$ は原始根である。

さて、以上が証明になりますが、もう少し調べると（といってもwikipediaに書いてる事実だったのですが）、この逆に近いことも言えることが分かりました。すなわち

$n \geq 1$ に対し、 $F_{n}$ を $F_{n} = 2^{2^{n}} + 1$ と定める。 $F_{n}$ が素数であることと、 $3^{\frac{F_{n} - 1}{2}} \equiv - 1 mod F_{n}$ が成り立つことは同値。

$3$ はフェルマー素数ととても関係が深い数だったのですね！

と興奮気味に書きましたが、この証明は簡単です。必要性は上記の証明の中で示しています。十分性について書きます。

十分性の証明

$3^{\frac{F_{n} - 1}{2}} \equiv - 1 mod F_{n}$ が成り立つならば、 $3^{F_{n} - 1} \equiv 1 mod F_{n}$ だから $3$ の $(Z / F_{n} Z)^{\times}$ における位数は $F_{n} - 1 = 2^{2^{n}}$ の約数であり、 $2^{k}$ の形。しかし、 $k = 2^{n} - 1$ では $3^{2^{k}} = 3^{(F_{n} - 1) / 2} \equiv - 1 mod F_{n}$ だから、 $3$ の位数はちょうど $2^{2^{n}}$ になる。これは $(Z / F_{n} Z)^{\times}$ の位数が $2^{2^{n}}$ であることを言っているので、 $F_{n}$ は素数である。

なお、wikipediaを見るとこの事実を用いて $F_{n}$ が $n = 7, 8, 10, 13, 14, 20, 22, 24$ でフェルマー素数でないことの証明に用いられたことが書いてあります（Pépin's test - Wikipedia）。

（この記事ははてなブログに筆者が書いた記事をmathlog用に書き直したものです）

投稿日：2020年9月6日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

triprod

2927

他の人のコメント

コメントはありません。

読み込み中

triprod

フェルマー素数の原始根について

導入
フェルマー素数の原始根
証明