(adsbygoogle = window.adsbygoogle || []).push({}); For each prime number p, let M_{p}be the number of solutions modulo p to the equation x² + y² = 1. Find a formula for M_{p}and prove it. [Use the fact that (-1,0) and (^{1-m²}/_{1+m²},^{2m}/_{1+m²}) for rational m give all rational solutions of x² + y² = 1. Divide into two cases whether p | 1+m² or not].

This was homework, but the assignment was handed in weeks ago. I never got this problem, but I am reviewing for my exam now, so I'd like to figure it out. I can understand that if (a/c, b/c) is a rational solution to x² + y² = 1, then if c is invertible modulo p, then (ac^{-1}, bc^{-1}) gives a solution to

[tex]x^2 + y^2 \equiv 1 (\mbox{mod } p)[/tex]

where c^{-1}is such that [itex]cc^{-1} \equiv 1 (\mbox{mod }p)[/itex]. But I don't see how exactly this will help me find M_{p}. I also don't see why every solution to the congruence must come from a rational solution to the equation. Finally, I don't know what to do when p | 1+m². Well, when that is the case, then -1 is a quadratic residue modulo p, and I know that the final answer is:

[tex]M_p = p - \left (\frac{-1}{p}\right )[/tex]

where [itex]\left (\frac{-1}{p}\right)[/itex] is a Legendre symbol, which is equal to 1 when x² = -1 (mod p) has a solution (i.e. -1 is a quadratic residue modulo p) and its equal to -1 when x² = -1 (mod p) has no solution (i.e. -1 is a nonresidue modulo p). This formula actually comes from:

[tex]M_p = (p+1) - \left (\left (\frac{-1}{p}\right ) + 1\right )[/tex]

So I think somehow, looking at the rational solutions to x² + y² = 1 gives p+1 solutions to the congruence, excpet for some possible over/undercounting. That over/undercounting is corrected for by the term:

[tex]-\left (\left (\frac{-1}{p}\right ) + 1\right )[/tex]

I see that [itex]\left (\frac{-1}{p}\right )[/itex] has to do with when p | 1 + m², since this would mean m² = -1 (mod p), so [itex]\left (\frac{-1}{p}\right ) = 1[/itex]. So somehow we find p+1 potential solutions. Note for each value of x such that there exists some y such that x² + y² = 1 (mod p), there are in fact exactly 2 y values that will work. So we had p+1 potential solutions, but when -1 is a quadratic residue modulo p, we must have accidentally counted the case of x = (1-m²)/(1+m²) (mod p), but when 1+m² = 0 (mod p) which actually isn't legal, so we have to eliminate two of the possible solutions.

However, the above is all very sketchy. That is, I have errant guesses as to why certain quantities are appearing in the final answer, but I don't think anything I've said above is very convincing.

So how is the formula for M_{p}derived? Thanks.

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# X² + y² = 1 (mod p)

**Physics Forums - The Fusion of Science and Community**