This is the full question:

show that if $p$ is an odd prime then the number of ordered pair solutions of the congruence$x^2-y^2 \equiv a \pmod p,$ is $p-1$ unless $a \equiv 0 \pmod p,$ in which case number of solutions is $2p-1$.

Considering $x,y \,\in \mathbb{Z}$. In the second case, since $a \equiv 0 \pmod p,$ it follows that $p\mid (x-y)(x+y)$, but then there will be infinitely many solutions of this congruence relation because there are no bounds mentioned in the question on $x$ and $y$.

So is the question incomplete? or is it implicitly stated that $0\leq x,y<p$ .For this bound, do we get $2p-1$ solutions?

  • 1
    $\begingroup$ The congruence is modulo $p$. Therefore, there are only $p$ possible values that either $x$ or $y$ could be under this constraint. You could say that $2$ and $p+2$ are both values of $x$, but there is no distinction between them modulo $p$. Now suppose that $x$ is some non-zero value. How many values of $y$ solve the given congruence? What changes if $x$ is $0$? $\endgroup$
    – abiessu
    Aug 26, 2019 at 20:52
  • 4
    $\begingroup$ They are not asking for integer solutions but equivalence class solutions. There are only $p$ equivalence classes so there are only $p^2$ pairs of $(x,y)$ at all. $\endgroup$
    – fleablood
    Aug 26, 2019 at 21:09

2 Answers 2


ETA: For whatever reason I thought the question here was to prove that the statement in the OP's thread in the shaded yellow box, which is what I did below.

You already answered your own question for the case where $a$ is zero so we now consider the case where $a$ is nonzero i.e., $a \in (\mathbb{F}_p)^{\times}$.

  1. Let $a \in (\mathbb{F}_p)^{\times}$. For every such nonzero $b \in (\mathbb{F}_p)^{\times}$, there is exactly one $c \in (\mathbb{F}_p)^{\times}$ satisfying $a=bc$.

  2. The above equation factors to $(x-y)(x+y) = a; x,y \in (\mathbb{F}_p)^{\times}$. By the above, for each nonzero $b=(x-y)\in (\mathbb{F}_p)^{\times}$, there is exactly one $c=(x+y)\in (\mathbb{F}_p)^{\times}$ such that $(x-y)(x+y)=a$.

  3. So for each nonzero $b\in (\mathbb{F}_p)^{\times}$, there is exactly one pair $(x,y); x,y \in (\mathbb{F}_p)^{\times}$ such that both $(x-y)=b$ and $(x-y)(x+y)=a$.

Can you finish from here.


Trying to find integer solutions $0\le x,y< p$ of $x^2-y^2\equiv 0 mod p$ as you observed implicates that $p\mid (x-y)(x+y)$, thus you see $p\mid x+y$ or $p\mid x-y$ since $p$ is prime. For every $1\le x<p$ you have the solutions $(x,y)=(x,p-x)$ and $(x,y)=(x,x)$ that are in total $2p-2$ couples, and for $x=0$ the unic solution $(x,y)=(0,0)$. They are $2p-1$ total solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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