$x^2 + y^2 = 0 \,\,(mod \,p)$ is congruent to $(\frac {x} {y})^2 = - 1 \,\,(mod \,p)$ how? So I'm working through this problem:
"For what primes p do there exist integers x and y with gcd(x, p) = 1 and gcd(y, p) = 1, such that x2 + y2 ≡ 0 (mod p)?" 
And I'm looking at the hint in the back of the book and it says:
"HINT: y has an inverse (mod p) --" [which I know, because they're coprime] "-- and x2 + y2 ≡ 0 (mod p) is equivalent to (x/y)2 ≡ - 1 (mod p)."

My question is, how is x2 + y2 ≡ 0 (mod p) equivalent to (x/y)2 ≡ - 1 (mod p)? Am I missing something really simple here, because I can't see how this is true.
 A: All the equations below are made $\mod p$.
We have
$-1 \equiv (\frac{x}{y})^2 \equiv (\frac{x}{y}) \cdot (\frac{x}{y})  \equiv (x y^{-1}) \cdot (x y^{-1}) \equiv x^2 (y^{-1})^2$
Then, multiplying by $y$ in both sides,
$-y \equiv x^2 (y^{-1})^2 y \equiv x^2 y^{-1}$
and multiplying both sides by $y$  again
$-y^2 \equiv x^2$
So, adding $y^2$ in both sides
$0 \equiv x^2 + y^2$
Therefore,
$-1 \equiv (\frac{x}{y})^2 \Rightarrow 0 \equiv x^2 + y^2$
But, from this proof, it's very easy to see that
$0 \equiv x^2 + y^2 \Rightarrow -1 \equiv (\frac{x}{y})^2 $
(just do the steps in the reverse order).
Thus, they are equivalent.
A: So now the question is: for which $p$ prime do $x^2+y^2$ has not trivial solutions in $\mathbb{Z}_p$?
The answer comes from the hint: for which primes $p$ the polynomial $z^2+1$ has a solution? And the answer to this is pretty simple: when $4|p-1$, when $4$ divides $p-1$. Why is that? It all comes from the fact that the multiplicative subgroup of a finite field is cyclic. There exist one element $g\in\mathbb{Z}_p$ such that $g^n$ generates all the elements of $\mathbb{Z}_p$. In particular we get that $$g^{p-1}= 1\mod{p}.$$
Removing the case in which $p=2$, we get that $p-1$ is always even and will get that $$g^{\frac{p-1}{2}}=-1\mod p.$$
It is clear that the answer to the question now is asking for an $n$ such that $$g^{2n}=-1\mod p$$ $$g^{4n}=1=g^{p-1}\mod p$$ which has always two solutions, $1$ and $p-1$. But will have $4$ solutions only when $4|p-1$.
P.S. BTW in case $p=2$: $$x^2+y^2=(x+y)^2\mod 2.$$ So basically $(0,0),(1,1)$ are solutions. It is trivial because the polynomial splits but still requires some attention.
