Der Chinesische Restsatz
Als Anwendung der Ergebnisse zeigen wir einen klassischen Satz über das simultane Lösen von Kongruenzen. Zur Motivation betrachten wir die Kongruenzen
x ≡ 2 mod(3) und x ≡ 4 mod(5).
Die erste Kongruenz hat die Lösungen
…, −1, 2, 5, 8, 11, 14 , …,
die zweite die Lösungen
…, −1, 4 , 9 , 14, 19, 24, …
Wir sehen, dass genau die ganzen Zahlen
…, −1, 14, 29, …
beide Kongruenzen simultan lösen. Es stellen sich die Fragen, ob und wann eine simultane Lösung zweier Kongruenzen immer existiert, und wie wir im Fall der Existenz eine Lösung effektiv berechnen können. Die Existenzfrage ist im Allgemeinen zu verneinen. Zum Beispiel haben die Kongruenzen
x ≡ 0 mod(2) und x ≡ 1 mod(6)
keine gemeinsame Lösung. Der folgende Satz besagt, dass für teilerfremde Moduln stets eine Lösung existiert, und dass diese Lösung modulo dem Produkt der Moduln eindeutig ist:
Satz (Chinesischer Restsatz)
Seien m1, m2 ≥ 1 teilerfremd, und seien a1, a2 beliebig. Weiter sei m = m1 m2. Dann gibt ein modulo m eindeutig bestimmtes x mit
(+) x ≡ a1 mod(m1) und x ≡ a2 mod(m2).
Beweis
zur Existenz:
Mit Hilfe des Euklidischen Algorithmus können wir 1 = (m1, m2) als Linearkombination von m1 und m2 darstellen. Seien also n1, n2 ∈ ℤ mit
1 = n1 m1 + n2 m2.
Nun setzen wir
x = a1 n2 m2 + a2 n1 m1.
Dann ist x wie gewünscht, da
x ≡ a1 n2 m2 ≡ a1(1 − n1 m1) ≡ a1 mod(m1),
x ≡ a2 n1 m1 ≡ a2(1 − n2 m2) ≡ a2 mod(m2).
zur Eindeutigkeit:
Sind x und x′ wie in (+), so gilt x ≡ x′ mod(m1) und x ≡ x′ mod(m2). Dann gilt m1|(x − x′) und m2|(x − x′). Wegen (m1, m2) = 1 gilt also m1 m2|(x − x′). Damit ist x ≡ x′ mod(m1m2).
Der konstruktive Beweis zeigt, wie sich die modulo m eindeutige Lösung berechnen lässt. Das Verfahren ist auch für große Moduln sehr effizient.
Beispiel
Wir lösen die obigen Kongruenzen
2 ≡ x mod(3) und 4 ≡ x mod(5)
mit dem Verfahren des Beweises. Der Euklidische Algorithmus liefert
1 = 2 · 3 − 1 · 5.
Damit ist
x = a1 n2 m2 + a2 n1 m1 = 2 · (−1) · 5 + 4 · 2 · 3 = −10 + 24 = 14
die modulo 15 eindeutige Lösung der Kongruenzen, in Übereinstimmung mit der oben durch Auflisten gefundenen Lösung.
Das Ergebnis lässt sich auf mehr als zwei Kongruenzen verallgemeinern:
Satz (Chinesischer Restsatz, allgemeine Form)
Sei r ≥ 2, und seien m1, …, mr ≥ 1 paarweise teilerfremd. Weiter seien a1, …, ar ≥ 1 beliebig. Dann gibt es ein modulo m = m1 … mr eindeutig bestimmtes x mit
(+) x ≡ ai mod(mi) für alle 1 ≤ i ≤ r.
Um eine Lösung von (+) effektiv zu bestimmen, können wir die beiden ersten Kongruenzen zu
x ≡ a12 mod(m1m2)
zusammenfassen, wobei a12 die modulo m1m2 eindeutige Lösung der beiden Kongruenzen ist. Damit haben wir ein äquivalentes System mit r − 1 Kongruenzen erzeugt. Die Wiederholung dieser Reduktion liefert schließlich die modulo m eindeutige Lösung des Systems.
Für den nicht teilerfremden Fall gilt (Übung):
Satz (Existenz simultaner Lösungen)
Sei r ≥ 2, und seien m1, …, mr ≥ 1 und a1, …, ar ≥ 1 beliebig. Dann gibt es genau dann ein x mit x ≡ ai mod(mi) für alle 1 ≤ i ≤ r, falls gilt
(mi, mj)|(ai − aj) für alle 1 ≤ i < j < r.
Eine Lösung ist modulo kgV( m1, …, mr) eindeutig bestimmt.