If $a$ is a quadratic residue of the prime $p= 8n+5,$ then the solutions of $x^2 \equiv a \ (\text{mod} \ p)$ are $x \equiv \pm a^{n+1}$ or $\pm 2^{2n+1}a^{n+1} \ (\text{mod} \ p)$

I have shown that $x \equiv \pm a^{n+1}$ or $\pm 2^{2n+1}a^{n+1} \ (\text{mod} \ p)$ are the possible solutions. How do I show they are all the possible solutions? Appreciate any advice, thank you.


1 Answer 1


$(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic of order $p-1$, generated by $b$ say. Let $a=b^n$ and $x=b^m$. Then $2m$ must agree with $n$, mod $p-1$. If $n$ is even then divide through by 2, so $m=n/2$ or $n/2+(p-1)/2$. If $n$ is odd then there is no solution. So either way there can't be more than two.

  • $\begingroup$ One really should justify why there cannot be more than $2$ solutions since that is the heart of the matter. Simply stating that it is true is far from a proof. $\endgroup$ Nov 8, 2018 at 15:06
  • $\begingroup$ Let $x=b^m$ say. Then $2m=n \bmod p-1$. $\endgroup$ Nov 8, 2018 at 15:11
  • $\begingroup$ That's a first step. You should finish it and add it to the answer. There are various ways to prove it but it was not at all clear which you had in mind. Answers should not leave such doubts. $\endgroup$ Nov 8, 2018 at 15:13
  • $\begingroup$ You are right and I have been more diligent. $\endgroup$ Nov 8, 2018 at 15:21
  • 1
    $\begingroup$ Well done. +1 $ $ $\endgroup$ Nov 8, 2018 at 15:24

You must log in to answer this question.

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