Der Chinesische Restsatz
Als Anwendung unserer Ergebnisse über zyklische Gruppen geben wir einen kurzen algebraischen Beweis des Chinesischen Restsatzes:
Satz (Chinesischer Restsatz)
Seien m1, …, mr ≥ 1 paarweise teilerfremde Zahlen, und seien a1, …, ar ≥ 1 beliebig. Dann gibt ein modulo m = m1 … mr eindeutig bestimmtes a ∈ ℤ mit a ≡ ai mod(mi) für alle 1 ≤ i ≤ n.
Beweis
Sei G = ℤm1 × … × ℤmr. Wir schreiben kurz ([ a1 ], …, [ ar ]) anstelle von ([ a1 ]m1, …, [ ar ]mr) für die Elemente von G. Da die mi teilerfremd sind, ist die Gruppe G isomorph zu ℤm, und sie wird erzeugt durch ([ 1 ], …, [ 1 ]). Also gibt es ein modulo m eindeutiges a ∈ ℤ mit
([ a1 ], …, [ ar ]) = a ([ 1 ], …, [ 1 ]) = ([ a ], …, [ a ]).
Dann ist aber ai ≡ a mod(mi) für alle 1 ≤ i ≤ r.
Beispiel
Wir betrachten die Kongruenzen
2 ≡ x mod(3) und 4 ≡ x mod(5).
Die modulo 15 eindeutige Lösung x erfüllt
([ 2 ]3, [ 4 ]5) = x ([ 1 ]3, [ 1 ]5) = φ([ x ])
mit dem Isomorphismus φ : ℤ15 → ℤ3 × ℤ5 mit
φ([ a ]15) = ([ a ]3, [ a ]5) = a ([ 1 ]3, [ 1 ]5) für alle 0 ≤ a < 15.
Damit ist x = 14 die modulo 15 eindeutige simultane Lösung der Kongruenzen (vgl. die obige Tabelle für φ).
Eine Tabelle für φ zu erstellen, aus der die Lösung abgelesen werden kann, ist zeitaufwendig. Der kurze Beweis ersetzt das effektive auf dem Euklidischen Algorithmus basierende Verfahren zur Lösung simultaner Kongruenzen nicht.