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 Dec 12 '18 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 Dec 12 '18 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 Dec 12 '18 at 8:43
  • $\begingroup$ @TobErnack Of course. You are right. Edited! $\endgroup$ – Aspiring Mathemagician Dec 12 '18 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$ – Aspiring Mathemagician Dec 12 '18 at 8:50

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.$


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.