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

一般に素数$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$は原始根である。

$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$は素数である。