Exercise 4.5.5* ($ax^2 + b y^2 \equiv c \pmod p$ is solvable if $p
mid ab$)

Question

Given any integers $a,b,c$ and any prime $p$ not a divisor of $ab$, prove that $ax^2 + b y^2 \equiv c \pmod p$ is solvable.

Richard Ganaye · Accepted Answer

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

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

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

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

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

\begin{proof} This is equivalent to proof that the equation $\overline{a} x^2 + \overline{b} y^2 = \overline{c}$ has a solution $(x,y) \in \F_p^2$ if $\overline{a} \overline{b} 
e \overline{0}$.

Consider the two subsets $A, B$ of $\F_p$, defined by
\begin{align*}
A &= \{\overline{a} x^2 \mid x \in \F_p\},\
B &= \{\overline{c} - \overline{b} y^2 \mid y \in \F_p\}
\end{align*}
Let $S = \{z^2 \mid z \in \F_p\}$ denote the set of squares in $\F_p$. We know that there are $(p-1)/2$ squares in $\F_p^*$, and $\overline{0}$ is a square, so 
$$\mathrm{Card}(S) = \frac{p+1}{2}.$$
Moreover, since $ \overline{a} 
e \overline{0}$ and $\overline{b} 
e \overline{0}$, the maps $u \mapsto \overline{a} u$ and $u \mapsto \overline{c} - \overline{b} u$ are bijections on $\F_p$, thus
$$\mathrm{Card}( A ) = \mathrm{Card}(B) = \frac{p+1}{2}.$$
If $A, B$ were disjoint, then  
$$p = \mathrm{Card}( \F_p ) \geq \mathrm{Card}( A  \cup B)  = \mathrm{Card}( A ) + \mathrm{Card}( B )  = p+1,$$
and we obtain the contradiction $p >p+1$, so $A \cap B 
e \varnothing$. This shows that there is some $x \in \F_p$ and some $y \in \F_p$ such that $\overline{a} x^2 = \overline{c} - \overline{b} y^2 $, so the congruence $ax^2 + b y^2 \equiv c \pmod p$ is solvable.
\end{proof}

Exercise 4.5.5* ($ax^2 + b y^2 \equiv c \pmod p$ is solvable if $p \nmid ab$)

Answers

Comments

Exercise 4.5.5* ($ax^2 + b y^2 \equiv c \pmod p$ is solvable if $p \nmid ab$)

Answers

Comments

Add answer