Sum of two squares modulo a prime in $4\mathbb Z + 1$ I am trying to find the number of solution of the equation
$$
x^2 + y^2 = 1
$$
in $\mathbb Z/p\mathbb Z$, where $p$ is a prime such that $p\in4\mathbb Z+1$.
Apart from the trivial solutions $(0,\pm 1)$ and $(\pm1, 0)$, there is no solution when $p=5$, but $(6,2)$ is also its solution when $p=13$. It seems that there exists nontrivial solutions for other moduli, but I do not see a regular pattern for them.
By an exhaustive search by a computer I strongly believe that if $p = 4n+1$ the number of the solutions is $4n$, though I do not see why.
I would be grateful if you could provide a clue.
 A: If $p\equiv1\pmod4$, then there exists an integer, call it $i$, such that $i^2\equiv-1\pmod p$. Using that $i$ you can rewrite the equation as
$$
1=x^2+y^2=(x+iy)(x-iy).
$$
Now let's take $u=x+iy$ and $v=x-iy$ as new variables. The mapping $(x,y)\mapsto(u,v)$ is bijective, because we can find an inverse mapping
$x=(u+v)/2$, $y=(u-v)/(2i)$.
It is hopefully easy to see why the equation
$$
1=uv
$$
has $p-1$ solutions. The above bijectivity shows that the original equation then also has $p-1$ solutions.
A: There is a nice "geometric" picture here.
If you have a non-degenerate conic then any line intersects it in two points (counting multiplicity, infinity, and algebraic extensions). 
So, if you can find any one point on the curve, then there is a one-to-one correspondence between lines passing through that point and points on the curve. (your given point corresponds to the tangent line)
If your chosen point lies in the ground field -- $\mathbb{Z} / p \mathbb{Z}$ in this case -- then there is a one-to-one correspondence between curves with a slope in $\mathbb{Z} / p \mathbb{Z}$ and points with coordinates in $\mathbb{Z} / p \mathbb{Z}$.
So if there are any solutions, then there are $p+1$ solutions if we count points "at infinity". So the answer to your question now boils down to showing there are two points at infinity.
What do points at infinity mean? The quickest explanation is algebraic: you can homogenize your equation by adding a new variable so that all terms have the same degree. In this case:
$$ X^2 + Y^2 = Z^2 $$
The projective points are coordinate triples $(X:Y:Z)$ where not all the terms are zero. However, $(X:Y:Z)$ and $(aX:aY:aZ)$ both refer to the same point.
The "ordinary" (affine) point with coordinates $(a,b)$ correspond to the projective point with coordinates $(a:b:1)$.
So my previous analysis says that there are $p+1$ distinct projective points. The points at infinity are the ones where $Z=0$, so if we plug that in, we get
$$ X^2 + Y^2 = 0 $$
and so we have two solutions: $(1:i:0)$ and $(1:-i:0)$, where $i$ is a solution to $t^2 + 1 = 0$. If $p$ is odd, then such an $i$ exists in $\mathbb{Z} / p \mathbb{Z}$ if and only if $p \equiv 1 \bmod 4$ (see quadratic residuosity).
Because we can always find at least one solution ($(1,0)$), this means we should see $p-1$ solutions when $p \equiv 1 \bmod 4$ and $p+1$ solutions when $p \equiv 3 \bmod 4$.

We can use the above recipe to derive a formula for the points. I'll describe it affinely. The line through $(1,0)$ with slope $m$ is given by the formula
$$ y = m(x-1) $$
If we plug this into our circle equation and solve, we get
$$ x^2 + (m(x-1))^2 = 1 $$
whose solutions are
$$ x=1 \qquad \qquad x = \frac{m^2-1}{m^2-1} $$
so the other point on the line with slope $m$ is
$$ \left( \frac{m^2-1}{m^2+1}, \frac{-2m}{m^2+1} \right) $$
This gives us all of the points on the circle other than $(1,0)$. It gives us that too, if we make the appropriate sense of $m=\infty$.
So we see that if $t^2 + 1 = 0$ has no solutions, then every value of $m$ gives us a point, so we have $p+1$ points. If $m^2 + 1 = 0$ has two solutions, then those don't give us points on the circle, and we get $p-1$ points. (Well, it gives us the aforementioned two points at infinity, which you aren't counting)
