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


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
    Commented Dec 12, 2018 at 6:01
  • $\begingroup$ @Dino By quadratic reciprocity? $\endgroup$ Commented Dec 12, 2018 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
    Commented Dec 12, 2018 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$ Commented Dec 12, 2018 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
    Commented Dec 12, 2018 at 7:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .