Simultane lineare Kongruenzen

Sind endlich viele Kongruenzen

vorgegeben, dann spricht man von einem System simultaner linearer Kongruenzen. Eine Aussage über die Lösungsmenge macht der Chinesische Restsatz: Es sei ein System so vorgegeben, daß paarweise teilerfremd sind. Setzt man

und wählt x_j so, daß für gilt, dann ist

eine Lösung des Systems. Das System ist bis auf Kongruenz modulo m eindeutig lösbar, d.h., mit x' sind genau diejenigen Elemente x'' weitere Lösungen, für die gilt

Beispiel

Es ist das System zu lösen, wobei 2, 3, 5 paarweise teilerfremd sind. Es gilt Die Kongruenzen haben die speziellen Lösungen . Das gegebene System ist eindeutig lösbar mit .

Hinweis: Systeme simultaner linearer Kongruenzen kann man benutzen, um die Lösung von nichtlinearen Kongruenzen mit dem Modul m auf die Lösung von Kongruenzen zurückzuführen, deren Modul Primzahlpotenzen sind.