Finding Formula for Mp & Proving It

[AKG]

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

$$x^2 + y^2 \equiv 1 (\mbox{mod } p)$$

where c^-1 is such that $cc^{-1} \equiv 1 (\mbox{mod }p)$. 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:

$$M_p = p - \left (\frac{-1}{p}\right )$$

where $\left (\frac{-1}{p}\right)$ 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:

$$M_p = (p+1) - \left (\left (\frac{-1}{p}\right ) + 1\right )$$

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:

$$-\left (\left (\frac{-1}{p}\right ) + 1\right )$$

I see that $\left (\frac{-1}{p}\right )$ has to do with when p | 1 + m², since this would mean m² = -1 (mod p), so $\left (\frac{-1}{p}\right ) = 1$. 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.

 

[AKG]

Note, the expression for the solutions to x² + y² = 1 in rationals comes from the fact that (-1,0) is one solution, and that the set of solutions is equal to the set of points that lie on both the unit circle and on some line passing through (-1,0) with rational slope. So (x,y) is a solution to the above iff (assuming (x,y) is not (-1,0)) there exists rational m such that:

x² + y² = 1
y = mx + m

Doing some basic algebraic manipulations gives (x,y) = (^1-m²/_1+m², ^2m/_1+m²). I tried doing a similar thing with my problem. (-1,0) is one solution, and every other solution (x,y) must lie on some line passing through (-1,0) with slope a/b, where a runs from 0 to p-1, and b runs from 1 to p-1. So we get y = (a/b)x + (a/b), and also x² + y² = 1 (mod p). Let m = a/b, then we get:

x² + y² = 1 (mod p)
x² + (mx + m)² = 1 (mod p)
(1 + m²)x² + 2m²x + (m²-1) = 0 (mod p)
(x+1)[(1+m²)x + (m²-1)] = 0 (mod p)

So either x+1 = 0 (mod p) or (1+m²)x + (m²-1) = 0 (mod p). We already know that x+1 = 0 (mod p) gives us the solution (-1,0). So what about:

(1+m²)x + (m²-1) = 0 (mod p)

If 1+m² = 0 (mod p), then the above equation gives m²-1 = 0 (mod p) which implies that a²/b² = 1 (mod p). So a = b or a = -b. So m = 1,-1. But this in turn implies that, since we started with 1+m² = 0 (mod p) that 2 = 0 (mod p) so p = 2. It's easy to check that M₂ = 2, so we can ignore this case. Note that the Legendre symbol $\left (\frac{-1}{2}\right )$ is not defined, so this doesn't necessary contradict the formula I originally claimed to be the right one for M_p, it just means that the given formula doesn't handle the case p = 2.

Anyways, if 1+m² is not congruent to 0 (mod p), then we should be able to write:

x = (1-m²)/(1+m²) (mod p)
x = (b²-a²)/(b²+a²) (mod p)

So what we want to do is count the number of possible x values we get when a runs from 0 to p-1, and b runs from 1 to p-1. By plugging in values for a and b, we get a number of x values. We get x = 1 iff we let a = 0. For x = 1, we only get one y value that will solve the original congruence, and that y value is 0. So we know two solutions (-1,0) and (1,0). All remaining solutions will come from looking at:

x = (b²-a²)/(b²+a²) (mod p)

as both a and b run independently from 1 to p-1. Moreover, for each such x value that we get, there will be two unique y values that will correspond to that X. So the final answer is:

$$M_p = 2 + 2\left |\left\{\frac{b^2-a^2}{b^2+a^2}\ (\mbox{mod }p)\ :\ 1 \leq a \leq p-1,\ 1 \leq b \leq p-1\right\}\right |$$

Now assuming that the formula $M_p = p - \left(\frac{-1}{p}\right )$ is correct for odd primes p, we see that:

$$\left |\left\{\frac{b^2-a^2}{b^2+a^2}\ (\mbox{mod }p)\ :\ 1 \leq a \leq p-1,\ 1 \leq b \leq p-1\right\}\right | = \frac{p-1}{2} - 1$$

when -1 is a quadratic residue modulo p, and when it is not, the number is:

$$\left |\left\{\frac{b^2-a^2}{b^2+a^2}\ (\mbox{mod }p)\ :\ 1 \leq a \leq p-1,\ 1 \leq b \leq p-1\right\}\right | = \frac{p-1}{2}$$

But $\frac{p-1}{2}$ is equal to the number of quadratic residues modulo p, so the cardinality of that set is equal the number of non-(-1) quadratic residues modulo p. Can we find a 1-1 correspondence between:

{x | x is not congruent neither -1 nor 0 (mod p) but there exists y such that y² = x (mod p)}

and

{^b²-a²/_b²+a² (mod p) | 1 < a,b < p-1}?

 

[AKG]

Looking at it some more, suppose we fix some b value. Then it's not hard to prove that:

|{^b²-a²/_b²+a² (mod p) | 1 < a < p-1}| = (p-1)/2

because we prove that if a and a' give the same number (mod p), then some simple algebra shows that a = +/- a. This means that for a ranging from 1 to (p-1)/2 we will get unique numbers (mod p), and for a ranging from (p+1)/2 to p-1, we'll just get the same numbers as we got when a ranged from 1 to (p-1)/2.

Now since we let b vary as well, this should prove that

$$\left |\left\{\frac{b^2-a^2}{b^2+a^2}\ (\mbox{mod }p)\ :\ 1 \leq a \leq p-1,\ 1 \leq b \leq p-1\right\}\right | \geq \frac{p-1}{2}$$

But in some cases, this shouldn't be. I've made some mistake somewhere, but what?

 

[Hurkyl]

IMHO, it's a lot easier to simply count the m's than it is to try and convert everything back into (a, b)'s. You already know how the correspondence between the m's and the points on your circle, so why switch to (a, b)'s?

 

[shmoe]

Note, the expression for the solutions to x² + y² = 1 in rationals comes from the fact that (-1,0) is one solution, and that the set of solutions is equal to the set of points that lie on both the unit circle and on some line passing through (-1,0) with rational slope. So (x,y) is a solution to the above iff (assuming (x,y) is not (-1,0)) there exists rational m such that:

x² + y² = 1
y = mx + m

You're concerned mod p, so you can take m to be an integer here.

Doing some basic algebraic manipulations gives (x,y) = (^1-m²/_1+m², ^2m/_1+m²). I tried doing a similar thing with my problem. (-1,0) is one solution, and every other solution (x,y) must lie on some line passing through (-1,0) with slope a/b, where a runs from 0 to p-1, and b runs from 1 to p-1. So we get y = (a/b)x + (a/b), and also x² + y² = 1 (mod p). Let m = a/b, then we get:

x² + y² = 1 (mod p)
x² + (mx + m)² = 1 (mod p)
(1 + m²)x² + 2m²x + (m²-1) = 0 (mod p)
(x+1)[(1+m²)x + (m²-1)] = 0 (mod p)

There shouldn't be much to do beyond here. Just look at the p choices of m. If (-1/p)=-1, all these give a quadratic. One solution is (-1,0), the other (1-m^2)/(m^2+1). It's no problem to show duplicate x's given this way correspond to m and -m, which give distinct y's (no double for m=0). Thus p+1 solutions.

If (-1/p)=1, there are p-2 choices of m that give a quadratic and solutions like above (plus the (-1,0) solution). When m^2+1 is zero, your quadratic is actually linear, and has only the solution (-1,0).

 

[Hurkyl]

Oh, I wanted to point out a geometric fact too:

When (m²+1) = 0 (mod p), you still get another point on the circle -- it just happens to be "at infinity", and so it's not a solution to your congruence.

 

[AKG]

Thanks anyways guys, I figured it out before reading your posts. I found it easier to ignore that stuff with rational m altogether, and work directly with a's and b's. It's easy to check that rather than having to let both a and b range from 1 to p-1, it suffices to have just a vary, and fix b. Then the rest is easy. I suppose if I started out just working with m, i.e. with only one thing varying, then I wouldn't have to do the work showing that you can go from having both a and b vary, to having just a vary. On the other hand, there would still be some work involved in showing that you can treat m as an integer. For example, what if m = 2/p? I mean if m = a/b where b is non-zero (mod p), then you can treat m as the integer ab^-1, where b^-1 is the multiplicative inverse of b (mod p). But what integer do you treat m as when m = 2/p? Or in general when m = a/p is not an integer?

 

[Hurkyl]

You wouldn't consider m = 2/p any more than, when working in the rationals, consider m = 2/0.

The only possible slopes for a non-vertical line modulo p are 0, 1, 2, ..., p-1.