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

ax2+bx+c 0(modp) (1)


Proof.  Since  gcd(p, 4a)=1,  multiplying (1) by 4a gives an equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath (http://planetmath.org/Equivalent3) congruenceMathworldPlanetmathPlanetmathPlanetmath

4a2x2+4abx+4ac 0(modp)

which may furthermore be written as


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

{y2b2-4ac(modp)    (2)2ax+by(modp).     (3)

Case 1:  b2-4ac is a quadratic residue(modp).  Then (2) has a root  y=y00,  and therefore also the second root  y=-y0.  The roots  y=±y0 are incongruent, because otherwise one had  p2y0  and thus  py0y02b2-4ac  which is not possible in this case.
Case 2:  b2-4ac0(modp).  Now (2) implies that  y0(modp),  whence the corresponding root x0 of the linear congruence (3) does not allow other incongruent roots for (1).
Case 3:  b2-4ac is a quadratic nonresidue(modp).  The congruence (2) cannot have solutions; the same concerns thus also (1).

Example.  Solve the congruence

4x2+6x-3 0(mod43).

We have  b2-4ac=36+443=84-2(mod43)  and the Legendre symbolMathworldPlanetmath

(-243)=(-143)(243)=-1(-1)= 1

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


which is satisfied by  y±16(mod43) as one finds after a little experimenting.  Then we have the two linear congruences  24x+6±16(mod43),  i.e.


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

x 8(mod43)orx 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