# A conjecture about quadratic residues given $p \equiv 5 \pmod 8$

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

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

Corollary

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.

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.

Remark

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?

• The assertion in the original problem is correct. – André Nicolas Mar 15 '15 at 2:33
• 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$? – Liebster Jugendtraum Mar 15 '15 at 2:50
• 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). – André Nicolas Mar 15 '15 at 2:59
• @AndréNicolas Yes, I do wish that :) Any effort is appreciated. Thanks a lot. – Liebster Jugendtraum Mar 15 '15 at 3:05
• Done, fairly short. A little trick about the quadratic character of $2$ was used. – 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$.
• 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 :) – Liebster Jugendtraum Mar 15 '15 at 3:13