Exercise 3.2.22* (Number of solutions $(x,y)$ of the congruence $a x^2 + by^2 \equiv 1 \pmod p$)

Question

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Suppose that $(ab, p) = 1$ and that $p >2$. Shows that the number of solutions $(x,y)$ of the congruence $a x^2 + by^2 \equiv 1 \pmod p$ is $p - \legendre{-ab}{p}$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Notation: Since $\legendre{a}{p}$ depends only of the class of $a$ modulo $p$, for $\alpha = [a]_p \in \Z/p\Z$, let us denote $\legendre{\alpha}{p} = \legendre{a}{p}$.

(I mimiced the already done Exercises 5.6, 5.7, 5.8 of Ireland-Rosen.)
\begin{proof} Let $p$ be an odd prime, and $N$ the number of solutions of the congruence $a x^2 + by^2 \equiv 1 \pmod p$. Write $\F_p = \Z/p\Z$ the field with $p$ elements.

Let $\alpha , \beta \in \F_p$ denote the classes of $a, b$ in $\F_p$: $\alpha =[a]_p, \beta = [b_p]$ (and $u = [x]_p, v = [y]_p)$. We suppose that $ab \wedge p  = 1$, so that $a 
ot \equiv 0, b 
ot \equiv 0 \pmod p$, thus $\alpha 
e 0, \beta 
e 0$.

Consider the conic in the plane $\F_p 	imes \F_p$ given by $$C= \{(u,v) \in \F_p	imes \F_p \mid \alpha u^2 + \beta v^2 = 1\},$$ so that $N = \mathrm{Card}\ C$. If we partition the set $C$ in subsets where $u$ takes a given value, we obtain
\begin{align*}
N = \mathrm{Card}\ C &=  \sum_{u\in \F_p} \mathrm{Card}\ \left\{ v \in \F_p \mid \alpha u^2 + \beta v^2 = 1 ight\}\
&= \sum_{u\in \F_p} \mathrm{Card}\ \left\{ v \in \F_p \mid v^2 = \beta^{-1}(1 - \alpha u^2)ight\}.\
\end{align*}
Put $\delta = \beta^{-1}(1 - \alpha u^2)$. Then $\mathrm{Card}\ \{ v \in \F_p \mid v^2 = \delta\}$ is the number of solutions in $\F_p$ of  $v^2 = \delta$, which is $1 + \legendre{\delta}{p}$ (see Problem 3.1.23). This remains true if $\delta = 0$. Therefore, using $\legendre{\beta^{-1}}{p} = \legendre{\beta}{p}$,
\begin{align*}
N &= \sum_{u \in \F_p} \left( 1 + \legendre{\beta}{p} \legendre{1 - \alpha u^2}{p} ight),
\end{align*}
thus
\begin{align}
N &= p + \legendre{\beta}{p} \sum_{u \in \F_p} \legendre{1 - \alpha u^2}{p}.
\end{align}
From $1 - \alpha u^2 = -\alpha( u^2  - \alpha^{-1})= -\alpha( u^2  + \gamma)$,  where $\gamma = - \alpha^{-1} 
e 0$, we obtain
\begin{align*}
N &= p + \legendre{\beta}{p} \legendre{-\alpha}{p}  \sum_{u \in \F_p} \legendre{u^2 + \gamma}{p},
\end{align*}
so
\begin{align}
N&= p + \legendre{-\alpha \beta} {p} \sum_{u \in \F_p} \legendre{u^2 + \gamma}{p}.
\end{align}
It remains to show that, for any $\gamma 
e 0$,
$$ \sum_{u \in \F_p} \legendre{u^2 + \gamma}{p} = -1.$$

Consider the particular case $ \beta = - \alpha$ (and as above, $\gamma = -\alpha^{-1}$), so that $\alpha u^2 + \beta v^2 = 1 \iff v^2 - u^2 = \gamma$. By equation (2), since $\legendre{-\alpha \beta}{p} = \legendre{\beta^2}{p} = 1$,
\begin{align}
\mathrm{Card}\ \{(u,v) \in \F_p 	imes \F_p \mid v^2 - u^2 = \gamma\} = p +  \sum_{u \in \F_p} \legendre{u^2 + \gamma}{p}.
\end{align}
But here we can compute directly $\mathrm{Card}\ \{(u,v) \in \F_p 	imes \F_p \mid v^2 - u^2 = \gamma\}$ by the change of variables $s = v+u, t= v-u$, equivalent to $u = \frac{s-t}{2}, v = \frac{s+t}{2}$. The equation $\gamma = v^2 - u^2 = (v+u) (v-u)$ becomes $\gamma = st$.

Let $S = \{(u,v) \in \F_p 	imes \F_p \mid v^2 - u^2 = \gamma\}, \  T = \{(s,t) \in \F_p 	imes \F_p \mid st = \gamma\}$. The maps
$$
\varphi
\left\{
\begin{array}{ccl}
S & 	o & T\
(u,v) & \mapsto & ( v+u, v-u),
\end{array}
ight.
\qquad
\psi
\left\{
\begin{array}{ccl}
T & 	o & S\
(s,t) & \mapsto & \left( \frac{s-t}{2}, \frac{s+t}{2} ight),
\end{array}
ight.
\qquad
$$
are correctly defined: if $(u,v) \in S$, $(v+u)(v-u) = v^2 - u^2 = \gamma$, so $(v+u, v-u) \in T$, and if $(s,t) \in T$, then $st = \gamma$, thus $(u, v) = \left( \frac{s-t}{2}, \frac{s+t}{2} ight)$ satisfies $v^2 - u^2 =  \left( \frac{s+t}{2} ight)^2 -  \left( \frac{s-t}{2} ight)^2 = st = \gamma$, so $\left( \frac{s-t}{2}, \frac{s+t}{2} ight) \in T$.

Moreover $\psi \circ \varphi = 1_S,\ \varphi \circ \psi = 1_T$: for all $(u,v) \in S$, and for all $(s,t) \in T$,
\begin{align*}
(\psi \circ \varphi)(u,v) &= \psi(v+u, v-u) = \left(\frac{ (v+u) - (v-u)}{2} , \frac{ (v+u) + (v-u)}{2}ight) = (u,v),\
(\varphi \circ \psi)(s,t) &= \varphi \left( \frac{s-t}{2}, \frac{s+t}{2} ight) = \left( \frac{s+t}{2} + \frac{s-t}{2}, \frac{s+t}{2} - \frac{s-t}{2} ight) = (s,t).
\end{align*}

This shows that $\varphi$ is bijective (and $\psi = \varphi^{-1})$. Therefore $\mathrm{Card}\ S = \mathrm{Card} \ T$.

Similarly, the maps
$$\xi
\left\{
\begin{array}{ccl}
\F_p^* & 	o & T\
s & \mapsto & (s, s^{-1} \gamma)
\end{array}
ight.
\qquad 
\zeta
\left\{
\begin{array}{ccl}
 T& 	o & \F_p^*\
(s, t) & \mapsto & s
\end{array}
ight.
$$
satisfy $\zeta \circ \xi = 1_{\F_p^*}, \ \xi \circ \zeta = 1_T$, thus $\zeta$ is a bijection. Therefore
$$\mathrm{Card}\ S = \mathrm{Card} \ T = \mathrm{Card} \ \F_p^* = p-1.$$
Then (2) gives
$$p - 1 = \mathrm{Card}\ S = p +  \sum_{u \in \F_p} \legendre{u^2 + \gamma}{p},$$
therefore
$$\sum_{u \in \F_p} \legendre{u^2 + \gamma}{p} = -1\qquad (\gamma 
e 0).$$
By equation (2),
\begin{align*}
N &= p - \legendre{-\alpha \beta} {p}\
& = p - \legendre{-ab} {p}.
\end{align*}
The number of solutions of the congruence $a x^2 + by^2 \equiv 1 \pmod p$ is $p - \legendre{-ab}{p}$.
\end{proof}

Exercise 3.2.22* (Number of solutions $(x,y)$ of the congruence $a x^2 + by^2 \equiv 1 \pmod p$)

Answers

Comments

Exercise 3.2.22* (Number of solutions $(x,y)$ of the congruence $a x^2 + by^2 \equiv 1 \pmod p$)

Answers

Comments

Add answer