Fermat数

hbghlyj

整数 $n \geqslant 2$, $F_{n}=2^{2^{n}}+1$ 为第 $n$ 个Fermat数. 设 $p$ 为 $F_n$ 的质因数. 证明
(i) $2 \bmod p$ 的阶 $\operatorname{ord}_{p}(2)=2^{n+1}$.
(ii) $2^{(p-1) / 2} \equiv 1 \bmod p$
(iii) $p=1+2^{n+2} k$ 对某个 $k \in \mathbb{N}$.
(iv) $F_4=65537$ 为质数.

---

source: Problem 7
Fermat primes (A019434): 3, 5, 17, 257, 65537
Proth's Theorem

hbghlyj

(i)$$2^{2^n}+1\equiv0\pmod p\implies2^{2^n}\equiv-1\pmod p\tag1$$
$$\implies2^{2^{n+1}}=(2^{2^n})^2\equiv1\pmod p\implies\operatorname{ord}_p(2)\mid2^{n+1}$$
假设$\operatorname{ord}_p(2)<2^{n+1}\implies\operatorname{ord}_p(2)\mid2^n\implies2^{2^n}\equiv1\pmod p$与(1)矛盾. 因此必有$\operatorname{ord}_p(2)=2^{n+1}$.
(ii) $F_n$为奇数, 所以$p>2$.
由 (i) 知 $\operatorname{ord}_p(2)=2^{n+1}$, 而$\operatorname{ord}_p(2)\midφ(p)=p-1$, 故$$p\equiv1\pmod{2^{n+1}}$$
当$n≥2$时得到$p\equiv1\pmod8$.
根据Legendre symbol的Theorem 8知, $2$ 是$\operatorname{mod}p$的二次剩余, 由Euler's criterion有$2^{(p-1) / 2} \equiv 1 \pmod p$
(iii) 由(ii)知 $2$ 是$\operatorname{mod}p$的二次剩余, 设$2\equiv r^2\pmod p$, 则$\color{red}{\operatorname{ord}_p(r)=2\operatorname{ord}_p(2)}\midφ(p)=p-1$, 故$$p\equiv1\pmod{2^{n+2}}$$见if a prime $p$ divides a Fermat Number then $p=k\cdot 2^{n+2}+1$? 与 Theorem 6 (Euler-Lucas)
(iv) 设$p$为$F_4$的质因数, 由(iii)知 $p=k\cdot2^6+1$.
$≤256$的$k\cdot2^6+1$型质数只有193, 而193不整除65537, 故65537为质数.

hbghlyj

hbghlyj 发表于 2023-1-28 15:33
设$2\equiv r^2\pmod p$, 则$\color{red}{\operatorname{ord}_p(r)=2\operatorname{ord}_p(2)}\midφ(p)=p-1$

红色等式的证明:
设$o=\operatorname{ord}_p(r)$. 则$r^o\equiv1\pmod p$.
$$2^o=r^{2o}\equiv1\pmod p\implies\operatorname{ord}_p(2)\mid o$$而$\operatorname{ord}_p(2)$为偶数, 故$o$为偶数, 设$o=2k$,$$r^{2\operatorname{ord}_p(2)}=2^{\operatorname{ord}_p(2)}\equiv1\pmod p\implies2k\mid 2\operatorname{ord}_p(2)\implies k\mid\operatorname{ord}_p(2)$$另一方面$$2^k=r^o\equiv 1\pmod p\implies\operatorname{ord}_p(2)\mid k$$故$k=\operatorname{ord}_p(2)$.