2
$\begingroup$

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

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?

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

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
3
  • $\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, 2015 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, 2015 at 3:17
  • $\begingroup$ I'll think about it. Hope I can come up with an alternative way :) $\endgroup$
    – Liebster Jugendtraum
    Mar 15, 2015 at 3:20

You must log in to answer this question.

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