congruence of arbitrary degree


TheoremMathworldPlanetmath.  A congruenceMathworldPlanetmathPlanetmathPlanetmathPlanetmath of nth degree and modulo a prime numberMathworldPlanetmath has at most n incongruent roots.

Proof.  In the case  n=1,  the assertion turns out from the entry linear congruence.  We make the induction hypothesis, that the assertion is true for congruences of degree less than n. 

We suppose now that the congruence

f(x):=anxn+an-1xn-1++a0 0(modp), (1)

where  pan,  has at least n incongruent roots x1,x2,,xn.  Form the congruence

f(x)an(x-x1)(x-x2)(x-xn)(modp). (2)

Both sides have the same term anxn of the highest degree, whence they may be cancelled from the congruence and the degree of (2) has a lower degree than n.  Because (2), however, clearly has n incongruent roots x1,x2,,xn,  it must by the induction hypothesis be simplifiable to the form  00(modp)  and thus be an identical congruence.

Now, if the congruence (1) had an additional incongruent root xn+1, i.e.  P(xn+1)0(modp), then the identical congruence (2) would imply

an(xn+1-x1)(xn+1-x2)(xn+1-xn) 0(modp).

Yet, this is impossible, since no one of the factors (http://planetmath.org/ProductMathworldPlanetmathPlanetmath) of the left hand side is divisible by p.  This settles the inductionMathworldPlanetmath proof.

Cf. http://eom.springer.de/c/c024860.htmSpringerLink.

Example.  When  f(x):=x5+x+10(mod7),  we have
f(0)1(mod7),
f(1)3(mod7),
f(2)32+2+10(mod7),
f(3)279+3+1-12+42(mod7),
f(4)(-3)5+4+1+2+50(mod7),
f(5)(-2)5+5+1-32+6-262(mod7),
f(6)(-1)5+6+16(mod7).
Thus only the representants 2 and 4 of a complete residue systemMathworldPlanetmath modulo 7 (see conditional congruences) are roots of the given congruense.  A congruence needs not have the maximal amount of incongruent roots mentionned in the theorem.

References

  • 1 K. Väisälä: Lukuteorian ja korkeamman algebran alkeet.  Tiedekirjasto No. 17. Kustannusosakeyhtiö Otava, Helsinki (1950).
Title congruence of arbitrary degree
Canonical name CongruenceOfArbitraryDegree
Date of creation 2013-03-22 18:52:29
Last modified on 2013-03-22 18:52:29
Owner pahio (2872)
Last modified by pahio (2872)
Numerical id 10
Author pahio (2872)
Entry type Theorem
Classification msc 11A05
Classification msc 11A07
Related topic SufficientConditionOfPolynomialCongruence
Related topic APolynomialOfDegreeNOverAFieldHasAtMostNRoots