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.

  • 2
    $\begingroup$ $p$ is a prime ? $\endgroup$ – DiffeoR Feb 20 '14 at 12:35
  • $\begingroup$ If $p=9$, the quadratic residues are $1,4,0,7,7,0,4,1,0$ and there are only $6$ solutions... $\endgroup$ – user21820 Feb 20 '14 at 12:56
  • $\begingroup$ @user21820 Are you just computing $x^2$ for $1,\ldots, 9$, and not $x^2 + y^2$ for all pairs? $\endgroup$ – Joe Tait Feb 20 '14 at 13:07
  • $\begingroup$ @JoeTait: Pairs of course. Did you get more than 6 solutions? If you count permutations, then 12. $\endgroup$ – user21820 Feb 20 '14 at 13:10
  • $\begingroup$ 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. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.