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.

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.$$
