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

$a{x}^2+bx+c\equiv \mathrm{\hspace{0.33em}0}(modp)$ (1)

is

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

• one, if  $b^2-4ac\equiv 0(modp)$;

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

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

$$4a^2{x}^2+4abx+4ac\equiv \mathrm{\hspace{0.33em}0}(modp)$$

which may furthermore be written as

$${(2ax+b)}^2\equiv b^2-4ac(modp).$$

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

$\{\begin{array}{cc}{y}^2\equiv b^2-4ac(modp)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}(2)\hfill & \\ 2ax+b\equiv y(modp).\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.25em}(3)\hfill & \end{array}$

Case 1:  $b^2-4ac$ is a quadratic residue$(modp)$.  Then (2) has a root  $y=y_0\ne 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(modp)$.  Now (2) implies that  $y\equiv 0(modp)$,  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$(modp)$.  The congruence (2) cannot have solutions; the same concerns thus also (1).

Example.  Solve the congruence

$$4x^2+6x-3\equiv \mathrm{\hspace{0.33em}0}(mod43).$$

We have  $b^2-4ac=36+4\cdot 4\cdot 3=84\equiv -2(mod43)$  and the Legendre symbol

$$\left(\frac{-2}{43}\right)=\left(\frac{-1}{43}\right)\left(\frac{2}{43}\right)=-1\cdot (-1)=\mathrm{\hspace{0.33em}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(mod43),$$

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

$$4x\equiv \pm 8-3(mod43)$$

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

$$x\equiv \mathrm{\hspace{0.33em}8}(mod43)\mathit{\hspace{1em}}\text{or}\mathit{\hspace{1em}}x\equiv \mathrm{\hspace{0.33em}12}(mod43).$$

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