Original Problem

$p$ is a prime that is congruent to $5$ modulo $8$ and $a$ is a quadratic residue modulo $p$.

Prove that excactly one of $x_1=a^{\frac{p+3}{8}},x_2=(2a)(4a)^{\frac{p-5}{8}}$ is the solution to the congruence $x^2 \equiv a \pmod p$.

What I have already proved

$x_1^2 \equiv a \pmod p$ if $a^{\frac{p-1}{4}} \equiv 1 \pmod p$.

$x_2^2 \equiv a \pmod p$ if $a^{\frac{p-1}{4}} \equiv -1 \pmod p$.


Assume that $a \equiv r \pmod p,\quad (1\leq r\leq p-1)$. Then $a^{\frac{p-1}{4}} \equiv r^{\frac{p-1}{4}} \pmod p$, and hence

(a). $x_1^2 \equiv a \pmod p$ if $r^{\frac{p-1}{4}} \equiv 1 \pmod p$.

(b). $x_2^2 \equiv a \pmod p$ if $r^{\frac{p-1}{4}} \equiv -1 \pmod p$.

Examining the cases where $p=5$ and $p=13$, I came up with a conjecture.


(I). $r^{\frac{p-1}{4}} \equiv 1 \pmod p$ if $r$ is odd.

(II). $r^{\frac{p-1}{4}} \equiv -1 \pmod p$ if $r$ is even.


Notice that $b^2 \equiv a \equiv r \pmod p$ for some nonzero integer $b$.

By Euler's Criterion, we have that $r^{\frac{p-1}{4}} \equiv (b^2)^{\frac{p-1}{4}} \equiv b^{\frac{p-1}{2}} \equiv \genfrac(){}{0}{b}{p} \pmod p$.

Equivalent form of the conjecture

(III). $b$ is a quadratic residue modulo $p$ if $r$ is odd.

(IV). $b$ is a quadratic nonresidue modulo $p$ if $r$ is even.

Can you prove or disprove (III) and (IV) using only the law of quadratic reciprocity?

  • $\begingroup$ The assertion in the original problem is correct. $\endgroup$ – André Nicolas Mar 15 '15 at 2:33
  • $\begingroup$ Well, a counterexample is found. Take $p=29,a=34$. Then $r=5$. $5 \equiv 11^2 \pmod {29}$ while $5^{\frac{29-1}{4}} \equiv 5^7 \equiv -1 \pmod {29}$, so the conjecture is not true. Anyway, can anyone think of a more straighforward way on determining whether $x_1$ or $x_2$ is the solution to the congruence $x^2 \equiv a \pmod p$? $\endgroup$ – Liebster Jugendtraum Mar 15 '15 at 2:50
  • $\begingroup$ Well, if you wish I could sketch the solution (I assigned essentially the same problem at least a couple of times in a beginning number theory course). $\endgroup$ – André Nicolas Mar 15 '15 at 2:59
  • $\begingroup$ @AndréNicolas Yes, I do wish that :) Any effort is appreciated. Thanks a lot. $\endgroup$ – Liebster Jugendtraum Mar 15 '15 at 3:05
  • $\begingroup$ Done, fairly short. A little trick about the quadratic character of $2$ was used. $\endgroup$ – André Nicolas Mar 15 '15 at 3:11

Let $p=8k+5$. By Euler's Criterion, $a^{4k+2}\equiv 1\pmod{p}$ and therefore $a^{2k+1}\equiv \pm 1\pmod{p}$.

Suppose that $a^{2k+1}\equiv 1\pmod{p}$. Then $a^{2k+2}\equiv a\pmod{p}$, and $a$ is congruent modulo $p$ to the square of $a^{k+1}$.

Now suppose that $a^{2k+1}\equiv -1\pmod{p}$. Since $p$ is of the form $8k+5$, it follows that $2$ is a quadratic non-residue of $p$, and therefore $2^{4k+2}\equiv -1\pmod{p}$. It follows that $2^{4k+2}a^{2k+1}\equiv 1\pmod{p}$, and therefore $$2^{4k+2}a^{2k+2}\equiv a\pmod{p}.$$ Thus the square of $2^{2k+1}a^{k+1}$, that is, of $(2a)(4a)^k$, is congruent to $a$ modulo $p$.

  • $\begingroup$ Well, actually my proof is exactly the same. I thought what you meant was to sketch an easier way, instead of examining $a^{\frac{p-1}{4}} \pmod p$, on determing whether $x_1$ or $x_2$ is the solution, because when $a$ and $p$ are fairly large, the calculation becomes complicated, using successive squaring, I guess? Sorry it's my bad. There was likely to be a misunderstanding. Anyway, thank you so much :) $\endgroup$ – Liebster Jugendtraum Mar 15 '15 at 3:13
  • $\begingroup$ Yes, I did not know what proof you had. As to the conjecture, you disposed of it. $\endgroup$ – André Nicolas Mar 15 '15 at 3:17
  • $\begingroup$ I'll think about it. Hope I can come up with an alternative way :) $\endgroup$ – Liebster Jugendtraum Mar 15 '15 at 3:20

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.