Fermat数

$n\geq 1$ のとき $x=2^{2^{n-1}}$ とおくと $x$ は $3$ で割り切れないから
$$F_n=x^2+1\equiv 2\Mod{3}$$
となる。
また、$n\geq 2$ のとき $y=2^{2^{n-2}}$ とおくと $y$ は $5$ で割り切れないから
$$F_n=y^4+1\equiv 2\Mod{5}$$
となる。最後に、$n\geq 2$ ならば $2^n\geq 4$ だから $F_n-1=2^{2^n}$ は $2^4=16$ で割り切れる。

$p$ を $a^{2^n}+b^{2^n}$ の奇数の素因数とする。$p$ が $a$ の素因数ならば $a, b$ は互いに素だから $p$ は $b$ の素因数ではないので $a^{2^n}+b^{2^n}$ は $p$ で割り切れなくなる。よって $p$ は $a$ の素因数ではないので、 合同式:定理5 より
$$ax\equiv b\Mod{p}$$
となる $x\Mod{p}$ が存在する。よって
$$a^{2^n}(1+x^{2^n})\equiv 0\Mod{p}$$
となるが、$p$ は $a$ の素因数ではないので、$p$ が奇数であることもあわせて
$$x^{2^n}\equiv -1\not\equiv 1\Mod{p}$$
となる。両辺を$2$乗し、
$$x^{2^{n+1}}\equiv 1\Mod{p}$$
となるから、$x\Mod{p}$ の乗法的位数は $2^{n+1}$ に一致する。 乗法的位数:定理1 より $p-1$ は $2^{n+1}$ で割り切れる。

$p$ を $F_n$ の素因数とする。
$$2^{2^n}\equiv -1\not\equiv 1\Mod{p}$$
となる。両辺を$2$乗し、
$$2^{2^{n+1}}\equiv 1\Mod{p}$$
となるから、$2\Mod{p}$ の乗法的位数は $2^{n+1}$ に一致する。よって、まずは
$p\equiv 1\Mod{2^{n+1}}$ が成り立つことがわかる。

$n\geq 2$ なので、$p\equiv 1\Mod{8}$ であるから、 平方剰余の第2補充法則 より
$$\left(\frac{2}{p}\right)=1$$
となる。このことから 平方剰余:定理2 より
$$2^{(p-1)/2}\equiv \left(\frac{2}{p}\right)=1\Mod{p}$$
となるが、$2\Mod{p}$ の乗法的位数は $2^{n+1}$ に一致するから、$2^{n+1}$ は $(p-1)/2$ を割り切る。
つまり $p-1$ は $2^{n+2}$ で割り切れる。

$F_n$ が素数で、かつ $(k/F_n)=-1$ ならば、 平方剰余:定理2 より
$$k^{(F_n-1)/2}\equiv\left(\frac{k}{F_n}\right)=-1\Mod{F_n}$$
となって、2. が成り立つ。
逆に 2. が成り立つとすると、
$$k^{F_n-1}\equiv 1\Mod{F_n}$$
より、$k\Mod{F_n}$ の乗法的位数は $F_n-1=2^{2^n}$ に一致するから、 乗法的位数:定理1 より
$F_n-1$ は $\varphi(F_n)$ を割り切る。つまり $\varphi(F_n)=F_n-1$ となる。よって 合同式:Eulerの定理 で述べたことから、$F_n$ は素数である。
またこのとき
$$\left(\frac{k}{F_n}\right)=k^{(F_n-1)/2}\equiv -1\Mod{F_n}$$
も成り立つから 1. が成り立つ。