- #1

AKG

Science Advisor

Homework Helper

- 2,565

- 4

*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.