Polynomkongruenz

Die Polynomkongruenz ist ein Begriff aus dem mathematischen Teilgebiet der Zahlentheorie. Es handelt sich dabei um eine Kongruenz, bei der auf beiden Seiten Polynome mit ganzzahligen Koeffizienten vorkommen. Ein Beispiel ist die Kongruenz

$x^4 + 2x + 1 \equiv x^3 - 6x^2 \pmod {13}$

Die normalisierte Darstellungsform einer solchen Kongruenz ist

$a_0 + a_1x + a_2x^2 + \ldots + a_nx^n \equiv 0 \pmod m$

Um diese Form zu erhalten, muss man teilweise die rechte Seite einer Kongruenz auf beiden Seiten subtrahieren.

Der Grad der Kongruenz ist der höchste Index i, für den a_i nicht durch m teilbar ist. Er ist vom Modul m abhängig und nicht mit dem Grad des entsprechenden Polynoms identisch. Man nennt ihn jedoch auch Grad des Polynoms modulo m. Für eine Kongruenz, bei der alle Koeffizienten durch den Modul teilbar sind, ist kein Grad definiert.

Zwei Polynome f(x) und g(x) sind identisch kongruent modulo m, wenn die Differenz f(x) − g(x) durch m teilbar ist. Man schreibt dann

$f(x) \equiv g(x) \pmod m$

Ganze Zahlen x, die

$f(x) \equiv 0 \pmod m$

erfüllen, heißen Wurzeln oder Lösungen der Polynomkongruenz. Gemeinsam mit dieser Lösung sind auch alle Elemente der zugehörigen Restklasse Lösungen. Zwei Wurzeln derselben Restklasse werden als nicht wesentlich verschieden angesehen und daher identifiziert; das entspricht dem Übergang von Z in den Restklassenring $\Z/(m)$. Ist m eine Primzahl, so ist $\Z/(m)$ ein Körper, und man hat die übliche Theorie der Polynome über Körpern, insbesondere kann eine Polynomkongruenz modulo einer Primzahl höchstens so viele Wurzeln $0\le x < m$ haben wie der Grad der Kongruenz. Ist m keine Primzahl, so gilt diese Aussage nicht mehr; so hat zum Beispiel die Polynomkongruenz

$x^4-1 \equiv 0 \pmod{16}$

vierten Grades die acht Wurzeln 1,3,5,7,9,11,13,15.

Quellen

• Karl-Heinz Indlekofer: Zahlentheorie. Birkhäuser, Stuttgart 1978, ISBN 3-7643-0942-3
• G.H. Hardy E.M. Wright: An Introduction to the Theory of Numbers, Oxford University Press (1979), ISBN 0-19-853171-0, Kap. VII: General Properties of Congruences