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

(1)

• 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 congruence $$4a^2x^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

Example. Solve the congruence $$4x^2+6x-3 \equiv 0 \pmod{43}.$$ We have $b^2\!-\!4ac = 36+4\cdot4\cdot3 = 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 \pm16 \pmod{43}$ as one finds after a little experimenting. Then we have the two linear congruences $2\cdot4x+6 \equiv \pm16 \pmod{43}$ , i.e. $$4x \equiv \pm8-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}.$$