$3$は$5$以上のフェルマー素数の原始根
この記事は インテジャーズのadvent calendar 7日目の記事です。
昨日の記事はコロちゃんぬさんによる「インテジャーズと私」というとても面白い記事でした。カスタマーレビューという発想が素晴らしかったです！
こちらの記事では、今年のmathpowerの耐久企画「正$65537$角形の作図」に関連した話題として、フェルマー素数の原始根について書きます。
ご存知のように、素数$p$がフェルマー素数の時、正$p$角形は作図可能です（←インテジャーズ文体を真似したつもりです）。
現在知られているフェルマー素数は$3,5,17,257,65537$の$5$個ですが、これらの$p$について正$p$角形の作図をしようとすると、（$p=17$くらいから）$\mathbb{F}_p$の原始根を一つ固定して考えたくなる状況が発生します。
正65537角形の作図方法についてUさんと検討していた時に、こんな感じの会話がありました。
Uさん「$p=17$の原始根って何でしょうね？（計算スラスラ）あー$3$は原始根ですね」
Uさん「$p=257$の原始根って何でしょうね？（PCカタカタ）あ、これも$3$がとれますね」
私「$3$優秀ですねww」
Uさん「じゃあ$p=65537$の原始根はどうなりますかね？」
私「まさか$3$なわけ、、」
Uさん「（PCカタカタ）おっ、これも$3$がとれますね」
私「ええ！？まじですか…！」
実際、$p=17$の時に$3^n \text{ 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,$$
$$3^9 \equiv 14, 3^{10} \equiv 8, 3^{11} \equiv 7, 3^{12} \equiv 4, 3^{13} \equiv 12, 3^{14} \equiv 2, 3^{15} \equiv 6, 3^{16} \equiv 1 $$
となっていて、$3$が原始根であることが比較的簡単に確認できます。
その他のフェルマー素数でも計算では確かめられるわけですが、この現象が「偶然なのか、理由があるのか」については、単に計算しただけでははっきりしません。
さて、その後調べ物をしているうちに、この現象には理由が付けられることが分かりました。一般に次の事実が成り立つことが知られています。
定理
$p$が$5$以上のフェルマー素数のとき、$(\mathbb{Z}/p\mathbb{Z})^{\times}$の生成元（原始根）として常に$3$が取れる。
常に、と書きましたが、現在知られている$5$以上のフェルマー素数は$5,17,257,65537$のたった$4$個です。これらの$4$個について$3$が原始根であることは（上記のように）計算すれば確かめられます。
もしフェルマー素数がこれ以降無いことが証明されてしまうと、この定理は威力を発揮しないまま終わってしまう悲しい状態になってしまうので、この事実を知って以降私はフェルマー素数はもっとたくさん存在して欲しいと思うようになりました。もしなんらかの方法で新たなフェルマー素数が発見された時、原始根として計算するまでもなく$3$が取れるのです！
（ただし後述するとおり、この逆に近い事実が成り立っており、これを用いてフェルマー数$F_n=2^{2^n}+1$が素数かどうかの判定を行うこともあるようです（Pépin's test））
ということでこの定理の証明を以下に行います。
（証明）
一般に素数$p$について、$(\mathbb{Z}/p\mathbb{Z})^{\times}$の原始根が常に存在する。それを一つとって$g$とする。任意の$a \in (\mathbb{Z}/p\mathbb{Z})^{\times}$に対して$a = g^{\nu (a)} $なる$\nu (a)$がmod $p-1$で一意に定まり、
$$\left( \frac{a}{p} \right) = (-1)^{\nu (a)} $$
と書ける。ここで $\left( \frac{a}{p} \right)$ は平方剰余記号。
さて、$g$は原始根だから、$g^{\frac{p-1}{2}} \equiv -1 $ mod $p$が成り立ち、
$$\left( \frac{a}{p} \right) = (-1)^{\nu (a)} \equiv (g^{\frac{p-1}{2}})^{\nu (a)}= (g^{\nu (a)})^{\frac{p-1}{2}} = a^{\frac{p-1}{2}} \text{ mod } p $$
が成り立つ（いわゆるEulerの規準）。
さて、$3$が原始根であることを言うには、$3^{\frac{p-1}{2}} \equiv -1 \text{ mod } p$を言えば良いが、上記により
$$\left( \frac{3}{p} \right) = -1 $$
を言えば良いことになる。ここで平方剰余の相互法則が使えて
$$\left( \frac{3}{p} \right) = (-1)^{\frac{3-1}{2}\frac{p-1}{2}} \left( \frac{p}{3} \right) = (-1)^{\frac{p-1}{2}} \left( \frac{p}{3} \right) $$
が成り立つが、今 $p = 2^{2^n}+1 \hspace{3mm} (n \geq 1)$より$\frac{p-1}{2} = 2^{2^n-1}$は偶数だから
$$\left( \frac{3}{p} \right) = \left( \frac{p}{3} \right) $$
となる。また、$p = 2^{2^n}+1 \equiv (-1)^{2^n}+1 =2 \text{ mod } 3$だから結局
$$\left( \frac{3}{p} \right) = \left( \frac{2}{3} \right) =-1 $$
となる。以上より
$$3^{\frac{p-1}{2}} \equiv -1 \text{ 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 \text{ mod } F_n$が成り立つことは同値。
と興奮気味に書きましたが、この証明は簡単です。必要性は上記の証明の中で示しています。十分性について書きます。
（十分性の証明）
$3^{\frac{F_n-1}{2}} \equiv -1 \text{ mod } F_n$が成り立つならば、$3^{F_n-1} \equiv 1 \text{ mod } F_n$だから$3$の$(\mathbb{Z}/F_n\mathbb{Z})^{\times}$における位数は$F_n-1=2^{2^n}$の約数であり、$2^k$の形。しかし、$k=2^n-1$では$3^{2^k} = 3^{(F_n-1)/2} \equiv -1 \text{ mod } F_n$だから、$3$の位数はちょうど$2^{2^n}$になる。これは$(\mathbb{Z}/F_n\mathbb{Z})^{\times}$の位数が$2^{2^n}$であることを言っているので、$F_n$は素数である。
（証明終了）
なお、wikipediaを見るとこの事実を用いて$F_n$が$n=7, 8, 10, 13, 14, 20, 22, 24$でフェルマー素数でないことの証明に用いられたことが書いてあります（Pépin's test - Wikipedia）。
以上で終わりとします。ここまでお読みいただきありがとうございます。
明日の記事はせきゅーんさんの記事「Szemerédi３」です！お楽しみに！！
