I've stumbled upon this congruence very similar to Fermat's Little Theorem, but I can't seem to wrap my head around how to solve it. It goes like this:
i) Suppose $p$ is prime, $(a,p)=1$ and the congruence $x^2 \equiv a \pmod p$ has a solution $x$. Prove that $a^{(p-1)/2}\equiv 1 \pmod p$.
And the same question but with an additional condition:
ii) Suppose $p$ is prime, $p \equiv 3 \pmod 4$, $(a,p) = 1$ and the congruence $x^2 \equiv a \pmod p$ does not have a solution $x$. Prove that $a^{(p-1)/2}\equiv -1 \pmod p$.
For i: Since $x^2 \equiv a \pmod p$ has a solution, we know that $p \mid x^2 – a$, hence $kp=x^2-a$ for some integer $k$, or $a = x^2-kp$. Now this doesn't really help me much!
For ii: Similarly stumped.
Best Answer
Hints:
(i) If $x^2 \equiv a \pmod p$ then what is $a^{\frac{p-1}{2}}$ as a power of $x$? Do this and apply Fermat's little theorem.
(ii) Write $x=a^{\frac{p-1}{2}}$. Fermat's little theorem gives you $x^2 \equiv 1 \pmod p$. Now use the rest of the information you've been given.