congruence of arbitrary degree

A congruence of $n$th degree and modulo a prime number 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

 $\displaystyle f(x)\;:=\;a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots+a_{0}\;\equiv\;0\pmod% {p},$ (1)

where  $p\nmid a_{n}$,  has at least $n$ incongruent roots $x_{1},\,x_{2},\,\ldots,\,x_{n}$.  Form the congruence

 $\displaystyle f(x)\;\equiv\;a_{n}(x-x_{1})(x-x_{2})\cdots(x-x_{n})\pmod{p}.$ (2)

Both sides have the same term $a_{n}x^{n}$ 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 $x_{1},\,x_{2},\,\ldots,\,x_{n}$,  it must by the induction hypothesis be simplifiable to the form  $0\equiv 0\pmod{p}$  and thus be an identical congruence.

Now, if the congruence (1) had an additional incongruent root $x_{n+1}$, i.e.  $P(x_{n+1})\equiv 0\pmod{p}$, then the identical congruence (2) would imply

 $a_{n}(x_{n+1}-x_{1})(x_{n+1}-x_{2})\cdots(x_{n+1}-x_{n})\;\equiv\;0\pmod{p}.$

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

Example.  When  $f(x):=x^{5}\!+\!x\!+\!1\equiv 0\pmod{7}$,  we have
$f(0)\equiv 1\pmod{7}$,
$f(1)\equiv 3\pmod{7}$,
$f(2)\equiv 32+2+1\equiv 0\pmod{7}$,
$f(3)\equiv 27\cdot 9+3+1\equiv-1\cdot 2+4\equiv 2\pmod{7}$,
$f(4)\equiv(-3)^{5}+4+1\equiv+2+5\equiv 0\pmod{7}$,
$f(5)\equiv(-2)^{5}+5+1\equiv-32+6\equiv-26\equiv 2\pmod{7}$,
$f(6)\equiv(-1)^{5}+6+1\equiv 6\pmod{7}$.
Thus only the representants 2 and 4 of a complete residue system 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 CongruenceOfArbitraryDegree 2013-03-22 18:52:29 2013-03-22 18:52:29 pahio (2872) pahio (2872) 10 pahio (2872) Theorem msc 11A05 msc 11A07 SufficientConditionOfPolynomialCongruence APolynomialOfDegreeNOverAFieldHasAtMostNRoots