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


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.

  • $\begingroup$ 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? $\endgroup$ – Dino Dec 12 '18 at 6:01
  • $\begingroup$ @Dino By quadratic reciprocity? $\endgroup$ – Lord Shark the Unknown Dec 12 '18 at 6:46
  • $\begingroup$ 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 $\endgroup$ – Dino Dec 12 '18 at 7:09
  • $\begingroup$ You need to work out $2^m$ modulo $7$ for $m=2^n$. The sequence $(2^m)$ is periodic modulo $7$. @Dino $\endgroup$ – Lord Shark the Unknown Dec 12 '18 at 7:18
  • $\begingroup$ 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}$ $\endgroup$ – Dino Dec 12 '18 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.