# Showing that $p$ is a Fermat prime if and only if every quadratic non-residue mod $p$ is also a primitive root mod $p$ [duplicate]

I want to show that $$p$$ is a Fermat prime $$\iff$$ every quadratic non-residue of $$p$$ is also a primitive root mod $$p$$
These are some facts that I know:

$$F_n = 2^{2^n} + 1$$
Every prime divisor $$p$$ of $$F_n$$ is of the form $$2^{k + 1}k + 1$$
$$\mathrm{ord}_{F_n}(2) = \mathrm{ord}_{p}(2) = 2^{n + 1}$$

This is what I wrote for the ($$\Rightarrow$$) direction and I want to make sure it is correct:
$$p = F_n = 2^{2^n} + 1$$ is prime, $$\phi(p) = p - 1 = 2^{2^n}$$
let $$a$$ be a quadratic non-reside mod $$p$$ so $$x^2 \equiv_p a$$ has no solutions. Suppose $$ord_p(a) = h$$. Since $$h \ | \phi(p) = 2^{2^n}$$ then $$h = 2^k$$ for some $$k \leq 2^{n}$$ Then $$(x^2)^h \equiv_p x^{2h} \equiv_p a^h \equiv_p 1$$ which is the same as $$x^{2^{k + 1}} \equiv_p 1$$ has no solutions therefore $$2^{k + 1}\nmid 2^{2^n}$$ We also know $$2^k \mid 2^{2^n}$$ so from these two we can conclude that $$2^k = 2^{2^n}$$ so the order of $$a$$ is $$\phi(p)$$ hence it is a primitive root mod $$p$$.

I don't know what to do for the other direction. Hints would be appreciated.

• Title: quadratic non-residue, not residue. This duplicate is also there. Commented Jan 9, 2021 at 14:58
• @DietrichBurde Thank you, I fixed the title. But that is a different question. My issue is showing that p is a Fermat number if every quadratic non-residue mod p is also a primitive root.
– Zara
Commented Jan 9, 2021 at 15:08
• @DietrichBurde The first is a different direction than my question, but I'm assuming I need the fact that the set of quadratic non-residues is equal to the set of primitive roots to show that p is of the form $2^{2^n} + 1$
– Zara
Commented Jan 9, 2021 at 15:09

We will use the fact that the set of quadratic non-residues mod $$p$$ is the same as the set of primitive roots mod $$p$$. Which means $$\phi(\phi(p)) = \phi(p - 1) = \frac{p - 1}{2}$$ Hence $$2 \mid p - 1$$ so we can write $$p = 2^km$$ where $$m$$ is odd. Since $$2^k$$ and $$m$$ are relatively prime and the Euler Phi function is multiplicative we have $$\phi(p - 1) = \phi(2^k)\phi(m) = 2^{k - 1}\phi(m) = \frac{p - 1}{2} = 2^{k - 1}m$$ thus $$m = \phi(m)$$ which means $$m = 1$$.
So now we have $$p - 1 = 2^k \rightarrow p = 2^k + 1$$. Now suppose $$k = 2^st$$ where $$t$$ is odd. Now we can write $$p = (2^{2^s})^t + 1$$. If $$t > 1$$ then $$p$$ could be factorised since $$t$$ is odd therefore $$t = 1$$ so now we have $$p = 2^{2^s} + 1 = F_s$$.