# Show $x^2+y^2 \equiv1\pmod p$ has $p-1$ solutions if $p \equiv1\pmod4$ and…

Question:

Show the equation $x^2+y^2 \equiv1\pmod p$ has $p-1$ solutions if $p \equiv1\pmod4$, and $p+1$ solutions if $p \equiv 3\pmod4$

I'm really stuck on this one. Any help would be highly appreciated.

• $p$ is a prime ? – DiffeoR Feb 20 '14 at 12:35
• If $p=9$, the quadratic residues are $1,4,0,7,7,0,4,1,0$ and there are only $6$ solutions... – user21820 Feb 20 '14 at 12:56
• @user21820 Are you just computing $x^2$ for $1,\ldots, 9$, and not $x^2 + y^2$ for all pairs? – Joe Tait Feb 20 '14 at 13:07
• @JoeTait: Pairs of course. Did you get more than 6 solutions? If you count permutations, then 12. – user21820 Feb 20 '14 at 13:10
• I see what you meant - I thought you were claiming you had listed all possible outcomes of $x^2 + y^2$, but you are pointing out that there are six pairs from the above that add to one. Sorry, just a misreading. – Joe Tait Feb 20 '14 at 13:18

If $p$ is a prime of the form $4k+1$,

Let $r$ be a primitive root mod $p$ (which can be proven by various means)

Let $i = r^k$

$i^2 = r^{2k} = -1$ (mod $p$) because $(i^2)^2 = r^{p-1} = 1$ (mod $p$)

If $1 = x^2-(iy)^2 = (x+iy)(x-iy)$,

Let $a = x+iy$

$x = (a+a^{-1})2^{-1}$

$y = (a-a^{-1})(2i)^{-1}$

Therefore there is a bijection between $\{ (x,y) : x^2+y^2 = 1 \space(\text{mod } p)\}$ and $\{ a : a \in [1..p-1] \}$

If $p$ is a prime of the form $4k+3$,

I can't prove it.

• Can anyone give a completely elementary proof for the second part? I'm still interested in seeing one. – user21820 Feb 21 '14 at 15:47