2
$\begingroup$

Suppose $p$ is a prime congruent to $3$ modulo 4. Additionally, suppose $a$ is a quadratic residue modulo $p$.
Prove that $x=a^{\frac{p+1}4}$ is a solution to the congruence $x^2\equiv a \pmod p$

I have no idea how to solve this. Can one use the Law of quadratic reciprocity ?

Since $a$ is a quadratic residue we know by eulers criterion that $a^{\frac{p-1}{2}} \equiv 1 \; mod \; p$

I dont know how to use the condition that $p\equiv 3 \pmod{4}$ from here on

$\endgroup$
1
  • $\begingroup$ No reciprocity, just Fermat's Theorem. $\endgroup$ Commented Jun 6, 2016 at 19:27

2 Answers 2

5
$\begingroup$

There is no need to use quadratic reciprocity, and I do not think it is helpful even.

Just try to check what is said:

Is it true that $(a^{\frac{p+1}{4}})^2 = a \pmod{p}$? That is, is it true that $a^{\frac{p+1}{2}} = a \pmod{p}$.

You have $a = b^2 \pmod{p}$ for some $b$ by assumption. So you'd need to show $b^{p+1} = b^2 \pmod{p}$.

To do this, recall Fermat's Little Theorem.

$\endgroup$
5
$\begingroup$

Let $x=a^{\frac{p+1}4}$. Then $x^2 =a^{\frac{p+1}2} = a^{\frac{p-1}2}\cdot a \equiv 1 \cdot a \bmod p$, by Euler's criterion.

The condition $ p \equiv 3 \bmod 4$ ensures that $\frac{p+1}4$ is an integer.

$\endgroup$

You must log in to answer this question.

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