# congruence of arbitrary degree

Theorem^{}. 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

$f(x):={a}_{n}{x}^{n}+{a}_{n-1}{x}^{n-1}+\mathrm{\dots}+{a}_{0}\equiv \mathrm{\hspace{0.33em}0}\phantom{\rule{veryverythickmathspace}{0ex}}(modp),$ | (1) |

where $p\nmid {a}_{n}$, has at least $n$ incongruent roots ${x}_{1},{x}_{2},\mathrm{\dots},{x}_{n}$. Form the congruence

$f(x)\equiv {a}_{n}(x-{x}_{1})(x-{x}_{2})\mathrm{\cdots}(x-{x}_{n})\phantom{\rule{veryverythickmathspace}{0ex}}(modp).$ | (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},\mathrm{\dots},{x}_{n}$, it must by the induction hypothesis be simplifiable to the form $0\equiv 0\phantom{\rule{veryverythickmathspace}{0ex}}(modp)$ 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\phantom{\rule{veryverythickmathspace}{0ex}}(modp)$, then the identical congruence (2) would imply

$${a}_{n}({x}_{n+1}-{x}_{1})({x}_{n+1}-{x}_{2})\mathrm{\cdots}({x}_{n+1}-{x}_{n})\equiv \mathrm{\hspace{0.33em}0}\phantom{\rule{veryverythickmathspace}{0ex}}(modp).$$ |

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.

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

Example. When $f(x):={x}^{5}+x+1\equiv 0\phantom{\rule{veryverythickmathspace}{0ex}}(mod7)$, we have

$f(0)\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(mod7)$,

$f(1)\equiv 3\phantom{\rule{veryverythickmathspace}{0ex}}(mod7)$,

$f(2)\equiv 32+2+1\equiv 0\phantom{\rule{veryverythickmathspace}{0ex}}(mod7)$,

$f(3)\equiv 27\cdot 9+3+1\equiv -1\cdot 2+4\equiv 2\phantom{\rule{veryverythickmathspace}{0ex}}(mod7)$,

$f(4)\equiv {(-3)}^{5}+4+1\equiv +2+5\equiv 0\phantom{\rule{veryverythickmathspace}{0ex}}(mod7)$,

$f(5)\equiv {(-2)}^{5}+5+1\equiv -32+6\equiv -26\equiv 2\phantom{\rule{veryverythickmathspace}{0ex}}(mod7)$,

$f(6)\equiv {(-1)}^{5}+6+1\equiv 6\phantom{\rule{veryverythickmathspace}{0ex}}(mod7)$.

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 |
---|---|

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 |