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.
 A: 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$
A: No. The way the question is worded, $p=2$ also works. 
Anyway, $y \neq 0 \pmod p,$ this means $y$ has a multiplicative inverse $\pmod p,$ for no better reason than $\gcd(y,p)=1$ and we have integers with $ys+pt=1.$
$$x^2 + y^2 \equiv 0 \pmod p,$$
$$x^2 \equiv -y^2 \equiv 0 \pmod p,$$
$$ \frac{x^2}{y^2} \equiv -1  \pmod p,$$
$$ \left( \frac{x}{y} \right)^2 \equiv -1  \pmod p.$$
A: by definition, there exists some $k$ so that $pk=x^2+y^2$. wlog, assume that $k$ is prime (otherwise look at its factorization etc.)
If $p$ does not divide $x$ or $y$, then $p^2$ does not divide $x^2+y^2$. But then, use this theorem (the top answer).
Since $p^1$ is an odd power, we deduce that $p \equiv 1 \mod 4$
A: Not an Elementary Proof
If you know anything about finite fields, then you can show that the group of units of a finite field $\mathbb{K}$ is cyclic (otherwise, you can show that there exists a positive integer $m<|\mathbb{K}|$ such that $x^m=x$ for all $x\in\mathbb{K}$, meaning that $|K|\leq m$, a contradiction).  If $C_n$ is the cyclic group of order $n\in\mathbb{N}$ and $d$ is a natural number such that $d\mid n$, then there exists an element $x\in C_n$ of order $d$.  
Combining these two observations, you get that the group of units of the field $\mathbb{F}_p$ of $p$ elements is the cyclic group $C_{p-1}$.  Hence, if a positive integer $d$ satisfies $d\mid p-1$, then there exists $x\in\mathbb{F}_p$ such that $x^d\equiv 1\pmod{p}$ but $x^j\not\equiv 1\pmod{p}$ for all positive integer $j<d$.  In particular, if $p\equiv 1\pmod{4}$, then $d=4$ leads to $x^4\equiv 1\pmod{p}$ but $x^2\not\equiv1\pmod{p}$, for some $x\in\mathbb{F}_p$.  Then, [...].  I leave the rest to you.
