Let $p=2^{2^k}+1$ be a prime where $k\ge1$. Prove that the set of quadratic non-residues mod $p$ is the same as the set of primitive roots mod $p$. Use this to show that $7$ is a primitive root mod $p$.

I've already shown the theorem to be true. The second part asks to use the first part to show the result which leads me to think that I have to show $7$ is a quadratic non-residue mod $p$ then use the first part to imply that it must be a primitive root.

To show $7$ to be a quadratic non-residue for $k\ge1$ is to show that the Legendre symbol $\left(\frac{7}{p}\right) = -1$. Now, $$\left(\frac{7}{p}\right)=\left(\frac{p}{7}\right)(-1)^{\left(\frac{7-1}{2}\right)\left(\frac{p-1}{2}\right)} = \left(\frac{p}{7}\right)(-1)^{3(2^{(2^k)-1})} = \left(\frac{p}{7}\right)$$ since $2^{2^k-1}$ is even (as $k\ge1$).

Then it suffices to know $p$ mod $7$ to determine the Legendre symbol. Since $\left(\frac{p}{7}\right) = -1$ when $p\equiv 3,5,6$ mod $7$, I suspect I somehow have to show that $p$ must be congruent to those values but I don't know how to do that. Although, trivially, $p\not\equiv 1$ mod $7$ otherwise, $7|2^{2^k}$ which is not possible.

Unfortunately, I don't know where to go from here.

Any guidance would be appreciated. However, assuming I’ve taken the right approach, I would prefer a constructive hint to a full blown solution, as I think I may be able to work it out on my own, given a nudge in the right direction.

Thank you for taking the time.

  • $\begingroup$ I am struggling with a VERY similar problem cough (and currently on mobile), but will try to assist. Notice, possibly from previous problems, we would really love to work mod 28, as that is what (7/p) 'uses'. What is p mod 7? What is p mod 4? So then what is p mod 28? $\endgroup$
    – Dino
    Commented Dec 12, 2018 at 8:28
  • $\begingroup$ I think your proof doesn't need to consider $k = 1$ as a special case since $2^{2^1-1} = 2$ is also even :) $\endgroup$
    – Tob Ernack
    Commented Dec 12, 2018 at 8:43
  • $\begingroup$ As for the question of computing the Legendre symbol, you can try to compute a few values of the sequence $2^{2^k} +1 \pmod 7$. Do you notice any patterns? You can also use some knowledge about the behavior of the sequence $2^x \pmod n$ for $x = 0, 1, 2, \ldots$ $\endgroup$
    – Tob Ernack
    Commented Dec 12, 2018 at 8:43
  • $\begingroup$ @TobErnack Of course. You are right. Edited! $\endgroup$ Commented Dec 12, 2018 at 8:49
  • $\begingroup$ @TobErnack I noticed this earlier, but didn't really know how to approach it rigorously. I will give it another try. $\endgroup$ Commented Dec 12, 2018 at 8:50

1 Answer 1


Powers of 2 are congruent to $1, 2, $ or $4$ modulo $7$ according as the power is congruent to $0, 1$ or $2$ modulo $3$ (as $3$ is the order of $2$ modulo $7$). As $3\nmid 2^k,$ $p\equiv 3\ or\ 5 \pmod 7.$


You must log in to answer this question.

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