Let $p$ be a prime number such that $p \not\equiv 3 \pmod{4}$. Show that there exist two integers $a$ and $b$, such that $a^2 + b^2 \equiv 0 \pmod{p}$ and $p \nmid a, b$.
If $p \not\equiv 3 \pmod{4}$ and $p$ is prime, $p$ must be of the form $4k+1$. But I don't know how to continue the problem. Can you help me, please? Thanks!
This is true because $-1$ is a quadratic residue modulo $p$. So there exist $x$ s.t.
$$x^2 \equiv -1 \pmod p \implies x^2 + 1^2 \equiv 0\pmod p$$
Hence the proof.
To prove that such an element exist we can use Wilson's Theorem. We then have $(p-1)! \equiv - 1 \pmod p$. Now use $p-k \equiv -k \pmod p$ and do this change for the numbers greater than $\frac{p-1}{2}$. Since you have even number of such factors the minus signs cancel out and you will have:
$$\left[\left( \frac{p-1}{2} \right)!\right]^2 \equiv - 1 \pmod p$$