Exercise 5.8.4 (Number of solutions of the congruence $x^2 + y^2\equiv 1 \pmod p$)

beginproof

(a)

We translate the problem in $\mathbb{Z}∕p\mathbb{Z}$. Let $X,Y,U,V$ denote the classes of $x,y,u,v$ in $\mathbb{Z}∕p\mathbb{Z}$. We write $0,1,2,\dots$ for the classes $\bar{0},\bar{1},\bar{2},\dots$ in $\mathbb{Z}∕p\mathbb{Z}$.

Suppose that $X,Y$ in $\mathbb{Z}∕p\mathbb{Z}$ satisfy $X^2+Y^2=1$ and $X\ne 1$. Then $1-X$ is invertible. Put $U=Y{(1-X)}^{-1}$, then

$$U^2+1=Y{(1-X)}^{-1}+1={(1-X)}^{-1}(Y+1-X).$$

Assume for the sake of contradiction that $U^2+1=0$. Then $X\ne 0$, otherwise $Y=\pm 1$, thus $U=Y{(1-X)}^{-1}=\pm 1$, and $U^2+1=2\ne 0$, because $p\ne 2$.

Since ${(1-X)}^{-1}\ne 0$, then $Y=X-1$, therefore

$$1=X^2+Y^2=X^2+{(X-1)}^2=2X^2-2X+1,$$

so $0=2X(X-1)$, which is impossible because $X\ne 0,X\ne 1$ (and $p\ne 2$). This shows that $U^2+1\ne 0$, so we may define

$$\begin{array}{lll}\hfill \{\begin{array}{cc}\hfill U& ={(1-X)}^{-1}Y,\hfill \\ \hfill V& ={(U^2+1)}^{-1}.\hfill \end{array}& & \hfill \text{(1)}\end{array}$$

Then

$$\begin{array}{llllll}\hfill U^2+1& ={(1-X)}^{-2}{Y}^2+1& \hfill & & \hfill & \\ \hfill & ={(1-X)}^{-2}(Y^2+{(1-X)}^2)& \hfill & & \hfill & \\ \hfill & ={(1-X)}^{-2}(X^2+Y^2-2X+1)& \hfill & & \hfill & \\ \hfill & =2{(1-X)}^{-2}(1-X)& \hfill (\text{since }{X}^2+Y^2=1)& & \hfill & & \hfill \\ \hfill & =2{(1-X)}^{-1}.& \hfill & & \hfill & \end{array}$$

Therefore (1) becomes

$$\begin{array}{lll}\hfill \{\begin{array}{cc}\hfill U& ={(1-X)}^{-1}Y,\hfill \\ \hfill V& =2^{-1}(1-X).\hfill \end{array}& & \hfill \text{(2)}\end{array}$$

This gives

$$2UV=2{(1-X)}^{-1}Y{2}^{-1}(1-X)=Y,$$

and $X=1-2V=(U^2-1)V$ (because $(U^2-1)V+2V=(U^2+1)V=1$), so

$$\begin{array}{lll}\hfill \{\begin{array}{cc}\hfill X& =(U^2-1)V,\hfill \\ \hfill Y& =2UV.\hfill \end{array}& & \hfill \text{(3)}\end{array}$$

In conclusion, for all $(X,Y)\in {(\mathbb{Z}∕p\mathbb{Z})}^2$, if $X^2+Y^2=1,X\ne 1$ then there are $(U,V)\in {(\mathbb{Z}∕p\mathbb{Z})}^2$ such that

$$\begin{array}{llll}\hfill & (U^2+1)V=1(\text{so }{U}^2+1\ne 0)& \hfill & \\ \hfill & \{\begin{array}{cc}\hfill X& =(U^2-1)V,\hfill \\ \hfill Y& =2UV.\hfill \end{array}& \hfill & \end{array}$$

(b)

Conversely, suppose that there are $(U,V)\in {(\mathbb{Z}∕p\mathbb{Z})}^2$ such that $$\begin{array}{llll}\hfill & (U^2+1)V=1& \hfill & \\ \hfill & \{\begin{array}{cc}\hfill X& =(U^2-1)V,\hfill \\ \hfill Y& =2UV.\hfill \end{array}& \hfill & \end{array}$$

Then

$$\begin{array}{llll}\hfill X^2+Y^2& ={[(U^2-1)V]}^2+4U^2{V}^2& \hfill & \\ \hfill & ={[(U^2+1)V]}^2& \hfill & \\ \hfill & =1,& \hfill & \end{array}$$

and $X\ne 1$, otherwise $Y=0$. Then $1=(U^2-1)V$, thus $V\ne 0$, and $0=2UV$, therefore $U=0$, $V=-1$. Then $1=(U^2+1)V=-1$. This gives the waited contradiction, because $1\ne -1$ in $\mathbb{Z}∕p\mathbb{Z}$ where $p\ne 2$. In conclusion

$$\begin{array}{llll}\hfill & X^2+Y^2=1,X\ne 1& \hfill & \\ \hfill & ⟺& \hfill & \\ \hfill & \exists <!--FUNCTION\; APPLICATION-->(U,V)\in {(\mathbb{Z}∕p\mathbb{Z})}^2,(U^2+1)V=1& \hfill & \\ \hfill & \text{and }\{\begin{array}{cc}\hfill X& =(U^2-1)V,\hfill \\ \hfill Y& =2UV.\hfill \end{array}& \hfill & \end{array}$$

(c)

Consider the two curves in the plans ${\mathbb{Z}}_p^2$: $$\begin{array}{llll}\hfill 𝒞& =\{(X,Y)\in {\mathbb{Z}}_p^2\mid X^2+Y^2=1\},& \hfill & \\ \hfill {𝒞}^{\prime }& =\{(U,V)\in {\mathbb{Z}}_p^2\mid (U^2+1)V=1\},& \hfill & \end{array}$$

and let $\phi$ be the map defined by

$$\phi \{\begin{array}{ccc}\hfill {𝒞}^{\prime }\hfill & \hfill \to \hfill & 𝒞\setminus \{(1,0)\}\hfill \\ \hfill (U,V)\hfill & \hfill \mapsto \hfill & ((U^2-1)V,2UV)\hfill \end{array}$$

Then $\phi$ is well defined, because $((U^2-1)V,2UV)\in 𝒞\setminus \{(1,0)\}$ by part (b).

Moreover $\phi$ is surjective (onto) by part (a).

We show that $\phi$ is injective (one-to-one). Suppose that $\phi (U,V)=\phi (U^{\prime },V^{\prime })$, where $(U,V)$ and $(U^{\prime },V^{\prime })$ are points on ${𝒞}^{\prime }$. Put $(X,Y)=\phi (U,V)=\phi (U^{\prime },V^{\prime })$. Then $X=(U^2-1)V$ and $Y=2UV$. Therefore $(U^2+1)V=1$ and

$$\begin{array}{llllll}\hfill (1-X)U& =[1-(U^2-1)V]U& \hfill & & \hfill & \\ \hfill & =[1+V-U^{2}V]U& \hfill & & \hfill & \\ \hfill & =(1+V+1-V)U& \hfill (\text{because }(U^2+1)V=1)& & \hfill & & \hfill \\ \hfill & =2UV& \hfill & & \hfill & \\ \hfill & =Y.& \hfill & & \hfill & \end{array}$$

Similarly $(1-X)U^{\prime }=Y$ thus $(1-X)U=(1-X)U^{\prime }$, where $X\ne 1$, thus $U=U^{\prime }$.

Therefore $(U^2-1)V=(U^2-1)V^{\prime }$ and $2UV=2U{V}^{\prime }$. If $U\ne 0$, the second equation shows that $V=V^{\prime }$, and if $U=0$, the first equation shows also $V=V^{\prime }$. So $(U,V)=(U^{\prime },V^{\prime })$. This shows that $\phi$ is injective.

Since $\phi$ is bijective,

$$Card({𝒞}^{\prime })=Card(𝒞\setminus \{(1,0)\}=Card(𝒞)-1.$$

We compute directly $Card({𝒞}^{\prime })$.

• If $\left(\frac{-1}{p}\right)=-1$, then for all $u\in {\mathbb{Z}}_p$, $u^2+1\ne 0$, thus

  $${𝒞}^{\prime }=\{(u,{(u^2+1)}^{-1})\mid u\in {\mathbb{Z}}_p\},$$

  thus $|{𝒞}^{\prime }|=p$, and

  $$|𝒞|=p+1.$$

• Suppose now that $\left(\frac{-1}{p}\right)=1$. There are exactly two values $u_0,-u_0$ of $u$ such that $u^2+1=0$. If $u\in \{u_0,-u_0\}$, there is no $v$ such that $0=(u^2+1)v=1$. If $u\notin \{u_0,-u_0\}$, $u^2+1\ne 0$, so there is exactly one $v$ such that $(u^2+1)v=1$:

  $${𝒞}^{\prime }=\{(u,{(u^2+1)}^{-1})\mid u\in {\mathbb{Z}}_p\setminus \{u_0,-u_0\}\},$$

  thus $|{𝒞}^{\prime }|=p-2$, and

  $$|𝒞|=p-1.$$

In either case,

$$|𝒞|=p-\left(\frac{-1}{p}\right).$$

The number of solutions of the congruence $x^2+y^2\equiv 1(modp)$ is

Note: For another proof with Gauss sums and Jacobi sums, see Ireland, Rosen p. 93, 94.