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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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?

share|cite|improve this answer
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$.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.