# quadratic congruence

Let $a,\,b,\,c$ be known integers and $p$ an odd prime number not dividing $a$.  The number of non-congruent roots of the quadratic congruence

 $\displaystyle ax^{2}\!+\!bx\!+\!c\;\equiv\;0\pmod{p}$ (1)

is

• two, if  $b^{2}\!-\!4ac$  is a quadratic residue modulo $p$;

• one, if  $b^{2}\!-\!4ac\equiv 0\pmod{p}$;

• zero, if  $b^{2}\!-\!4ac$  is a quadratic nonresidue modulo $p$.

Proof.  Since  $\gcd(p,\,4a)=1$,  multiplying (1) by $4a$ gives an equivalent (http://planetmath.org/Equivalent3) congruence

 $4a^{2}x^{2}\!+\!4abx\!+\!4ac\;\equiv\;0\pmod{p}$

which may furthermore be written as

 $(2ax\!+\!b)^{2}\;\equiv\;b^{2}\!-\!4ac\pmod{p}.$

Accordingly, one can obtain the the solution of the given congruence from the solution of the pair of congruences

 $\displaystyle\begin{cases}y^{2}\;\equiv\;b^{2}\!-\!4ac\pmod{p}\qquad\qquad(2)% \\ 2ax\!+\!b\;\equiv\;y\pmod{p}.\;\qquad\qquad(3)\\ \end{cases}$

Case 1:  $b^{2}\!-\!4ac$ is a quadratic residue$\pmod{p}$.  Then (2) has a root  $y=y_{0}\neq 0$,  and therefore also the second root  $y=-y_{0}$.  The roots  $y=\pm y_{0}$ are incongruent, because otherwise one had  $p\mid 2y_{0}$  and thus  $p\mid y_{0}\mid y_{0}^{2}\equiv b^{2}\!-\!4ac$  which is not possible in this case.
Case 2:  $b^{2}\!-\!4ac\equiv 0\pmod{p}$.  Now (2) implies that  $y\equiv 0\pmod{p}$,  whence the corresponding root $x_{0}$ of the linear congruence (3) does not allow other incongruent roots for (1).
Case 3:  $b^{2}\!-\!4ac$ is a quadratic nonresidue$\pmod{p}$.  The congruence (2) cannot have solutions; the same concerns thus also (1).

Example.  Solve the congruence

 $4x^{2}+6x-3\;\equiv\;0\pmod{43}.$

We have  $b^{2}\!-\!4ac=36+4\cdot 4\cdot 3=84\equiv-2\pmod{43}$  and the Legendre symbol

 $\left(\frac{-2}{43}\right)\;=\;\left(\frac{-1}{43}\right)\left(\frac{2}{43}% \right)\;=\;-1\cdot(-1)\;=\;1$

(see values of the Legendre symbol) says that $-2$ is a quadratic residue modulo 43.  The congruence corresponding (2) is

 $y^{2}\;\equiv\;-2\pmod{43},$

which is satisfied by  $y\equiv\pm 16\pmod{43}$ as one finds after a little experimenting.  Then we have the two linear congruences  $2\cdot 4x+6\equiv\pm 16\pmod{43}$,  i.e.

 $4x\;\equiv\;\pm 8-3\pmod{43}$

corresponding (3).  The first of them,  $4x\equiv 5\pmod{43}$,  is satisfied by  $x=12$  and the second,  $4x\equiv-11\pmod{43}$,  by  $x=8$.  Thus the solution of the given congruence is

 $x\;\equiv\;8\pmod{43}\quad\mbox{or}\quad x\;\equiv\;12\pmod{43}.$
 Title quadratic congruence Canonical name QuadraticCongruence Date of creation 2013-03-22 17:45:30 Last modified on 2013-03-22 17:45:30 Owner pahio (2872) Last modified by pahio (2872) Numerical id 11 Author pahio (2872) Entry type Theorem Classification msc 11A15 Classification msc 11A07 Related topic LinearCongruence Related topic LegendreSymbol Related topic QuadraticFormula Related topic ConditionalCongruences Defines quadratic congruence