Exercise 2.2.10 (Number of solutions of $x^2 - y^2 \equiv a \pmod p$)

Proof. Write ${𝔽}_p$ the field with $p$ elements. Let $\alpha ={[a]}_p$ denote the class of $a$ modulo $p$, and consider the sets

We want to prove that $S_a$ and $T_a$ have same cardinality. Consider the maps

These definitions make sense:

• If $(u,v)\in S_a$, then $(s,t)=(u+v,u-v)$ satisfies $\mathit{st}=(u+v)(u-v)=u^2-v^2=a$, so $(u+v,u-v)=(s,t)\in T_a$.

• If $(s,t)\in T_a$, then $(u,v)=({[2]}_p^{-1}(s+t),{[2]}_p^{-1}(s-t))$ (where ${[2]}_p$ is invertible, because $p$ is an odd prime) satisfies

  $$u^2-v^2=(u+v)(u-v)=({[2]}_p^{-1}(s+t)+{[2]}_p^{-1}(s-t))({[2]}_p^{-1}(s+t)-{[2]}_p^{-1}(s-t))=\mathit{st}=\alpha ,$$

  so $({[2]}_p^{-1}(s+t),{[2]}_p^{-1}(s-t))=(u,v)\in S_a$.

Moreover

(because

Therefore $\phi$ is bijective, and this proves

Now the cardinality of $T_a$ is more easy to compute.

• Assume that $\alpha \ne 0$, and consider the maps

  $$\chi \{\begin{array}{ccc}\hfill {𝔽}_p^{\text{∗}}\hfill & \hfill \text{→}\hfill & T_a\hfill \\ \hfill s\hfill & \hfill \mapsto \hfill & (s,\alpha s^{-1}),\hfill \end{array}\xi \{\begin{array}{ccc}\hfill T_a\hfill & \hfill \to \hfill & {𝔽}_p^{\text{∗}}\hfill \\ \hfill (s,t)\hfill & \hfill \mapsto \hfill & s.\hfill \end{array}$$

  (here $s(\alpha s^{-1})=\alpha$, so $(s,\alpha s^{-1})\in T_a$.)

  Then, for all $s\in {𝔽}_p^{\text{∗}}$,

  $$(\xi \circ \chi )(s)=\xi (s,\alpha s^{-1})=s,$$

  and for all $(s,t)\in {𝔽}_a$, $\mathit{st}=\alpha$, thus $\alpha s^{-1}=t$, so

  $$(\chi \circ \xi )(s,t)=\chi (s)=(s,\alpha s^{-1})=(s,t).$$

  This shows $\xi \circ \chi =1_{{𝔽}_p^{\text{∗}}},\chi \circ \xi =1_{T_a}$, so that $\xi$ is bijective, and

  $$|S_a|=|T_a|=|{𝔽}_p^{\text{∗}}|=p-1.$$

  Therefore the number of solutions of the congruence $x^2-y^2\equiv a(\mathit{mod}p)$ is $|S_a|=p-1$ if $a\not\equiv 0(\mathit{mod}p)$.

• Assume that $\alpha =0$ (i.e. $a\equiv 0(\mathit{mod}p)$). Since $\mathit{st}=0⟺s=0\text{ or }t=0$ in the field ${𝔽}_p$,

  $$\begin{array}{llll}\hfill T_0=\{(0,0),& (1,0),(2,0),\dots ,(p-1,0),& \hfill & \\ \hfill & (0,1),(0,2),\dots ,(0,p-1)\}.& \hfill & \end{array}$$

  Therefore

  $$|S_0|=|T_0|=2(p-1)+1=2p-1.$$

To conclude, the number of solutions of the congruence $x^2-y^2\equiv a(\mathit{mod}p)$ is $p-1$ unless $a\equiv 0(\mathit{mod}p)$, in which case the number of solutions is $2p-1$. □