PlanetMath: quadratic congruence

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

quadratic congruence

(Theorem)

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

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

(1)

two, if $b^2\!-\!4ac$ is a quadratic residue modulo ;
one, if $b^2\!-\!4ac \equiv 0 \pmod{p}$ ;
zero, if $b^2\!-\!4ac$ is a quadratic nonresidue modulo .

Proof. Since $\gcd(p,\,4a) = 1$ , multiplying (1) by gives an equivalent congruence

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

which may furthermore be written as

$\displaystyle (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

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

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

. 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

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

$\displaystyle 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

$\displaystyle \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

is a quadratic residue modulo 43. The congruence corresponding (2) is

$\displaystyle 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.

$\displaystyle 4x \equiv \pm8-3 \pmod{43}$

corresponding (3). The first of them, $4x\equiv 5 \pmod{43}$ , is satisfied by

and the second, $4x\equiv -11 \pmod{43}$ , by

. Thus the solution of the given congruence is

$\displaystyle x \equiv 8 \pmod{43}$ or $\displaystyle \quad x \equiv 12 \pmod{43}.$

"quadratic congruence" is owned by pahio.

(view preamble)

Also defines:

quadratic congruence

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: values of the Legendre symbol, Legendre symbol, linear congruence, implies, congruences, solution, congruence, quadratic nonresidue, quadratic residue, number, prime number, odd, integers

This is version 6 of quadratic congruence, born on 2008-01-25, modified 2008-01-27.
Object id is 10211, canonical name is QuadraticCongruence.
Accessed 684 times total.

Classification:

AMS MSC:	11A07 (Number theory :: Elementary number theory :: Congruences; primitive roots; residue systems)
	11A15 (Number theory :: Elementary number theory :: Power residues, reciprocity)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact