# Number of solutions to a given congruence problem

I am working through Irelands Number theory book. Below is ex7. ch.5

By direct calculation, show that if $p\nmid a$ then the number of solutions to $x^{2}\equiv y^{2}+a\pmod{p}$ is $p-1$ and if $p|a$ the number of solution is $2p-1$. (Hint: use the change of varialbes $u=x+y$, and $v=x-y$.)

By a previous problem we have that $\sum^{p-1}_{y=0}1+(\frac{y^{2}+a}{p})$ is the number of solutions to $x^{2}=y^{2}+a \pmod{p}$ where $(\frac{y^{2}+a}{p})$ is the Legendre symbol. I think I understand the case when $p\nmid a$ since there are as many residues$\pmod{p}$ as there are nonresidues. My confusion is about the case when $p|a$ and I don't know how to use the hint. Thanks.

-
can you please name the book @edison ? it might help me too , i would want to have a look at it –  Bhargav Feb 10 '12 at 17:28
When $a\equiv 0 \pmod p$, we can take $x-y$ any non zero, $x+y$ zero, or $x-y$ zero, $x+y$ any non-zero, or both zero, total $(p-1)+(p-1)+1$. –  André Nicolas Feb 10 '12 at 18:09
@Bhargav, the name of the book is, A classical introduction to modern number theory, by Kenneth Ireland and Michael Rosen. –  Edison Feb 10 '12 at 19:16
@AndréNicolas, thanks for the comment. –  Edison Feb 10 '12 at 19:16

If $p|a$, then $x^2\equiv y^2+a\pmod{p}$ if and only if $x^2\equiv y^2\pmod{p}$, if and only if $x^2-y^2\equiv 0\pmod{p}$, if and only if $(x+y)(x-y)\equiv 0\pmod{p}$, if and only if $uv\equiv 0\pmod{p}$. How many different solutions does this equation have?

-
Thanks for this comment –  Edison Feb 10 '12 at 16:32

First note that for example the congruence $x^2\equiv y^2 +1 \pmod{1}$ has $2$ solutions, and $x^2 \equiv y^2+0$ has $2$ solutions, so the result is not correct when $p=2$. However, it is correct when $p$ is an odd prime, so from now on assume that $p>2$.

By a direct calculation, what I would mean is a genuinely direct calculation, without any Legendre symbol stuff. Arturo Magidin has done the harder part. We deal with the case $a\equiv 0\pmod{p}$.

Since our congruence is equivalent to $x^2-y^2\equiv a \pmod{p}$, we are solving $(x-y)(x+y)\equiv 0\pmod p$.

To count the solutions, note that we can (i) let $x-y$ have any non-zero value $b$, ($p-1$ possibilities) and let $x+y\equiv 0$, or (ii) let $x-y \equiv 0$, and let $x+y$ take on any non-zero value, or (iii) let $x-y$ and $x+y$ each be congruent to $0$.

In the first case, $x-y\equiv b$, $x+y\equiv 0$ has a unique solution. This is where things break down in the case $p=2$, for you will recall from high-school algebra that solving $x-y=c$, $x+y=d$ involves dividing by $2$.

So there are $p-1$ type (i) solutions, $p-1$ type (ii) solutions, and $1$ type (iii) solution, for a total of $2(p-1)+1$. Alternately, count the solutions with $x-y\equiv 0$ (there are $p$ of them), the solutions with $x+y \equiv 0$ (another $p$). Add. But we have double-counted $(0,0)$, so the correct answer is $2p-1$.

A Legendre symbol calculation will also work. The only problem is that it somewhat distances us from what is going on.

For the case $a\equiv 0$, we want $$\sum^{p-1}_{y=0}\left(1+\left(\frac{y^{2}+0}{p}\right)\right)$$ (I have used your expression, with outer parentheses added.) This is $$\sum^{p-1}_{y=0} 1 + \sum^{p-1}_{y=0}\left(\frac{y^{2}}{p}\right).$$ The first sum is obviously $p$. For the second, note that $\left(\frac{0}{p}\right)=0$, and if $y\not\equiv 0$, then $\left(\frac{y^2}{p}\right)=1$, so the second sum is $p-1$.

-

Let $N$ denote the number of solutions to $x^2 - y^2 \equiv a \mod p$. Let $e(\alpha) = e^{2\pi \imath \alpha}$ so that $e(\alpha+\beta)=e(\alpha)e(\beta)$. Finally, let $\displaystyle \sum_{x=0}^{p-1} e\left(\frac{sx^2}p\right) = G(s;p)$.

\begin{eqnarray*} N &=& \frac 1p \sum_{s=0}^{p-1} \sum_{x,y=0}^{p-1} e\left(\frac{s(x^2-y^2-a)}p\right) = p + \frac 1p \sum_{s=1}^{p-1} e\left(\frac{-sa}p\right)\sum_{x,y=0}^{p-1} e\left(\frac{s(x^2-y^2)}p\right)\\ &=& p + \frac 1p \sum_{s=1}^{p-1} e\left(\frac{-sa}p\right)G(s;p)G(-s;p) \end{eqnarray*}

If $p$ is an odd prime, then it is well known that $G(s;p) = \left(\frac sp\right)\imath^{\left(\frac{p-1}2\right)^2} p^{\frac 12}$. It can be shown that $\left(\imath^{\left(\frac{p-1}2\right)^2}\right)^2 = \left(\frac{-1}p\right)$.

Hence, our sum becomes \begin{eqnarray*} &=& p + \frac 1p \sum_{s=1}^{p-1} e\left(\frac{-sa}p\right) \cdot\left(\frac{s}p\right)\left(\frac{-s}p\right)\left(\frac{-1}p\right)p\\ &=& p + \sum_{s=1}^{p-1} e\left(\frac{-sa}p\right)\\ &=& p + \begin{cases} -1 &\mbox{ if } a \not\equiv 0 \mod p\\ p-1 &\mbox{ if } a \equiv 0 \mod p \end{cases} \end{eqnarray*}

The result follows from here.

If $p$ is even, then $G(s;p)=0$ so I assume the question was for odd primes $p$.

-