"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?
Best 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.