Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've noticed a type of sum for the number of solutions of a type of quadratic form. For example, the number of solutions to $X^2-Y^2\equiv a\pmod{p}$ for $p$ an odd prime is given by the sum

$$\sum_{Y=1}^p(1+\left(\frac{Y^2+a}{p}\right))$$

where $\left(\frac{Y^2+a}{p}\right)$ is the Legendre symbol. It seems that the trick is to isolate the $X^2$, add 1 to the RHS, and then let $Y$ range over a complete residue system. It seems that for each value $Y$ takes, there will either be 2 or 0 solutions added to the running total. Is there a simple explanation why this is true?

I suspect that for each $y$ that is a solution, we could take both $x$ and $-x$ to get two solutions $(x,y)$ and $(-x,y)$? My only concern is when $x\equiv -x\pmod{p}$, in which case we would have $x\equiv 0\pmod{p}$. Why does the formula still work in that case as well? Thanks for any explanation.

share|improve this question
add comment

2 Answers

This is a general (and well-known) trick. The number of solutions to the congruence $$x^2\equiv f(y)\pmod{p}$$ for a polynomial $f$ is $$\sum_{y=0}^{p-1}\left[1+\left(\frac{f(y)}{p}\right)\right].$$ The reason for this is that the congruence $x^2\equiv a$ (mod $p$) always has $1+(x/p)$ solutions. Note that when $a\equiv0$ (mod $p$) the only solution to $x^2\equiv0$ (mod $p$) is $x\equiv0$ (mod $p$) but this is in accord with $(0/p)=0$.

share|improve this answer
    
Thanks for the quick reply! Let me see if I understand this correctly. For each value that $y$ takes, we essentially treat $f(y)$ as a new $a$? Is there a reason why you wrote $1-(f(y)|p)$ as opposed to $1+(f(y)|p)$ in the sum? –  cromarty Oct 25 '10 at 7:13
    
Yes: each value of $y$ gives $1+(f(y)/p)$ solutions $(x,y)$. –  Robin Chapman Oct 25 '10 at 8:38
add comment

It's a composition of two obvious facts. First, over a finite ring $\rm\:R\:$, any formula that counts the roots of a univariate polynomial extends to bivariate polynomials since the number of roots of $\rm\:f(X,Y)\:$ is simply the sum of the number of roots of $\rm\:f(X,r)\:$ for all $\rm\ r\in R\:$. Second, for quadratic polynomials over some finite field $\rm\:\mathbb F_p\:$ with $\rm\:p\:$ odd, the problem of root counting reduces to testing if the discriminant is a square, hence there exists an elementary closed-form root counting formula expressed in terms of the Legendre symbol. Apply these two observations immediately yields the formula at hand.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.