From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: how many solutions to modular equation?
Date: 9 Jul 1998 15:50:00 GMT

Robin Chapman  <rjc@maths.ex.ac.uk> wrote:

>I feel a theorem coming on:
Just lie down until the feeling passes :-)

>Let P be an odd prime, and let a and b be integers coprime to p. Then
>the congruence x^2 - a y^2 = b (mod p) has p - (a/p) solutions where
>(a/p) is the Legendre symbol.

Of course the "right" answer is to study the solutions to the
homogeneous equation  x^2-ay^2=bz^2  in  P^1. You have enumerated 
solutions of the form  [x,y,1], but we should add in the solutions of
the form  [x,y,0]. Here   y  cannot be zero, so setting  y=1 gives the
equation  x^2=a, which has  1 + (a/p) solutions. So the total number
of solutions in  P^1  is exactly  p+1, which

	1. is faster to type

	2. restores the symmetry between  a  and  b; indeed, the
		result then also counts the solutions to homogeneous
		quadratic equation over  F_p

	3. is reminiscent of the result for cubic equations, that the
		number of points in an elliptic curve over F_p  is
		p+1 + epsilon, where  |epsilon| <= 2sqrt(p)

At that point, of course, one begins to stumble on quite a bit of
machinery from algebraic geometry which estimates the number of points
in projective varieties over finite fields, but as is well known even for
elliptic curves over  F_p, the exact enumeration of the points is
extremely subtle.

dave