2
$\begingroup$

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.

1 Answers 1

6

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

  • 0
    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?2010-10-25
  • 0
    Yes: each value of $y$ gives $1+(f(y)/p)$ solutions $(x,y)$.2010-10-25