Polynomkongruenzen

Sind paarweise teilerfremde Zahlen, dann ist die Kongruenz

dem System

äquivalent. Ist k_j die Anzahl der Lösungen von für , dann ist die Anzahl der Lösungen von Man kann also die Lösung von Kongruenzen

wobei Primzahlen sind, auf die Lösung von Kongruenzen zurückführen. Diese wiederum lassen sich wie folgt auf Kongruenzen vom Primzahlmodul p zurückführen:

1. Jede Lösung von ist auch Lösung von
2. Jede Lösung von bestimmt unter der Bedingung, daß f'(x₁) nicht durch p teilbar ist, eine einzige Lösung modulo
   Sei Man setzt x=x₁+pt₁ und ermittelt die modulo p eindeutig bestimmte Lösung t₁' der linearen Kongruenz

   Setzt man t₁=t₁'+pt₂ in x=x₁+pt₁ ein, dann erhält man Man ermittelt nun die modulo p² eindeutig bestimmte Lösung t₂' der linearen Kongruenz

   und erhält durch Einsetzen von t₂=t₂'+pt₃ in daß x=x₃+p³t₃ gilt. Durch Fortsetzung des Verfahrens erhält man die Lösung der Kongruenz

Beispiel

Es ist die Kongruenz zu lösen. Aus folgt d.h. Wegen f'(x)=4x³+7 und ist zunächst die Lösung der Kongruenz gesucht: d.h. t₁=1+3t₂ und
Weiter betrachtet man und erhält als Lösung d.h. t₂=2+3t₃ und . Also ist 22 die modulo 27 eindeutig bestimmte Lösung von .