If $x^2+y^2 \equiv 0\pmod{p}$, then $p \equiv 1 \pmod{4}$ 
Prove that if $x^2+y^2 \equiv 0\pmod{p}$ where $p$ is a prime and $x,y$ are not both divisible by $p$, then $p \equiv 1 \pmod{4}$.

I tried using that $x^2 \equiv -y^2 \pmod{p}$ and conjectured that $-1$ must a quadratic residue modulo $p$, but I am not sure how that would help.

Since $p \not \mid y$, there exists integer $y'$ such that $yy' \equiv 1 \pmod p$. Then multiply both side of the congruence with $y'$ to get that:
$$(xy')^2 \equiv -(yy')^2 \equiv - 1 \pmod p$$
So hence $-1$ is a quadratic residue modulo $p$. To prove that $p \equiv 1 \pmod 4$ from this note that:
$$1 \equiv x^{p-1} \equiv (x^2)^{\frac{(p-1)}{2}} \equiv (-1)^{\frac{(p-1)}{2}} \pmod p$$
This implies that $\frac{(p-1)}{2}$ is even and hence $p \equiv 1 \pmod 4$
