2
$\begingroup$

Let $p$ be a prime which is $5 \pmod {8}$. Let $r$ be an element of $\mathbb{Z}/p\mathbb{Z}^*$ of order $4$ and let $a$ be a quadratic residue modulo $p$. Prove that a solution of $x^{2}=a \pmod p$ is given by either $x=a^{(p+3)/8}$ or $x=ra^{(p+3)/8}$.

I tried showing $a^{(p+3)/4}=a \pmod p$, but I couldn't figure out how to proceed.

2 Answers 2

3

You are on the right path. Let's try to prove that $a^{(p+3)/4}\equiv a \pmod{p}$. This is not always true, so our proof will run into a stumbling block. However, the stumbling block will tell us what the fix might be. (Conveniently, we are told what it is!)

To prove $a^{(p+3)/4}\equiv a \pmod{p}$ is equivalent to proving that $a^{(p-1)/4}\equiv 1 \pmod{p}$. Since $a$ is a quadratic residue, say $a\equiv b^2\pmod{p}$, we have $a^{(p-1)/4}\equiv b^{(p-1)/2}\equiv \pm 1\pmod p$. If you prefer, you may express this in terms of order. The order of $a^{(p-1)/4}$ is either $1$ or $2$.

If $a^{(p-1)/4}$ has order $1$, we are finished. What about if the order is $2$? Then $a^{(p+3)/4}\equiv -a \pmod{p}$. Awfully close, except for that unfortunate minus sign. That's where the $r$ of the statement of the problem comes to the rescue.

0

Hint, if $r$ is an element of order $4$, then $r^2=?$.

$a^{(p+3)/4}=a \pmod p$ might not be true....