# The set of the primitive roots modulo $p$, with $p$ a fermat prime

"Let $$p$$ be a prime of the form $$2^{2^{n}}+1$$, with $$n \in \mathbb{N}$$ (This means $$p$$ is a Fermat prime)

Using Euler's Criterion, prove that the set of primitive roots mod $$p$$ is equal to the set of quadratic non-residues mod $$p$$.

Use this to show 7 is a primitive root mod $$p$$"

I'll work up to the point I am stuck:

Suppose $$a$$ is a primitive root of mod $$p$$

Then $$ord_{p}(a)=p-1=2^{2^{k}}$$

(This means $$a^{2^{2^{k}}}\equiv 1$$ $$\text{mod}$$ $$p$$)

Euler's Criterion tells us:

$$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}$$ $$\text{mod}$$ $$p$$

From our defintions:

$$a^{\frac{p-1}{2}}= a^{2^{2^{k}-1}} \equiv a^{2^{-1}}$$ $$\text{mod}$$ $$p$$

Is correct so far? Where do i go from here? And is this a sufficient method to prove the sets are the same?

## 1 Answer

Use the criterion that $$a$$ is a primitive root modulo $$p$$ iff $$a^{(p-1)/q}\not\equiv1\pmod p$$ for all prime factors $$q$$ of $$(p-1)$$. Here $$p-1=2^{2^n}$$ so the only relevant $$q$$ is $$q=2$$.

In your question you wrote $$a^{2^{-1}}\pmod p$$. I don't know what you mean by that.

• Your idea makes complete sense! How would we then show that 7 is a primitive root mod p? By showing it's a quadratic non-residue? How do we do that? – Dino Dec 12 '18 at 6:01
• @Dino By quadratic reciprocity? – Lord Shark the Unknown Dec 12 '18 at 6:46
• So that tells us $\left(\frac{7}{p}\right) = \left(\frac{p}{7}\right)$, so I need to know the value of $p$ mod $7$. I have no idea how to work out that? I think its the multiple powers that are throwing me off – Dino Dec 12 '18 at 7:09
• You need to work out $2^m$ modulo $7$ for $m=2^n$. The sequence $(2^m)$ is periodic modulo $7$. @Dino – Lord Shark the Unknown Dec 12 '18 at 7:18
• I recognise it is 4,2,4,2..., but how do you show it without just brute forcing it? I can't pull out a multiple of 7 easily out of $2^{m}$ – Dino Dec 12 '18 at 7:37