Chinesischer Restsatz

Simultane Kongruenzen und Lösungsmenge

Eine simultane Kongruenz ganzer Zahlen ist ein System linearer Kongruenzen

x ≡ a₁ (mod m₁), …, x ≡ aₙ (mod mₙ).

Gesucht sind alle ganzen Zahlen x, die sämtliche Bedingungen gleichzeitig erfüllen. Existiert eine Lösung x₀, dann sind genau die Zahlen x₀ + kM mit k ∈ ℤ Lösungen, wobei M = kgV(m₁, m₂, …, mₙ) das kleinste gemeinsame Vielfache der Moduln ist. Es kann auch vorkommen, dass keine Lösung existiert.

Teilerfremde Moduln: Satz und Konstruktion

Der klassische chinesische Restsatz behandelt den Fall paarweise teilerfremder natürlicher Zahlen m₁, …, mₙ. Für jedes Tupel ganzer Zahlen a₁, …, aₙ existiert dann eine ganze Zahl x mit

x ≡ aᵢ mod mᵢ für i = 1, …, n.

Alle Lösungen sind kongruent modulo M = m₁m₂⋯mₙ. Wegen der Teilerfremdheit stimmt dieses Produkt mit dem kgV der Moduln überein.

Eine Lösung lässt sich mit dem erweiterten euklidischen Algorithmus bestimmen. Setze Mᵢ = M/mᵢ. Für jedes i sind mᵢ und Mᵢ teilerfremd. Daher gibt es ganze Zahlen rᵢ und sᵢ mit

rᵢmᵢ + sᵢMᵢ = 1.

Mit eᵢ = sᵢMᵢ gilt eᵢ ≡ 1 mod mᵢ und eᵢ ≡ 0 mod mⱼ für j ≠ i. Deshalb ist

x = Σᵢ₌₁ⁿ aᵢeᵢ

eine Lösung des gesamten Systems.

Beispiel mit den Moduln 3, 4 und 5

Gesucht ist x mit

x ≡ 2 mod 3, x ≡ 3 mod 4, x ≡ 2 mod 5.

Hier gilt M = 3 · 4 · 5 = 60 sowie M₁ = 20, M₂ = 15 und M₃ = 12. Der erweiterte euklidische Algorithmus liefert:

7 · 3 + (−1) · 20 = 1, also e₁ = −20; 4 · 4 + (−1) · 15 = 1, also e₂ = −15; 5 · 5 + (−2) · 12 = 1, also e₃ = −24.

Damit erhält man x = 2 · (−20) + 3 · (−15) + 2 · (−24) = −133. Wegen −133 ≡ 47 mod 60 sind alle Lösungen kongruent zu 47 modulo 60.

Der allgemeine Fall und ein Rätsel

Sind die Moduln nicht teilerfremd, kann eine Lösung trotzdem existieren. Eine Lösung existiert genau dann, wenn für alle i ≠ j gilt:

aᵢ ≡ aⱼ mod ggT(mᵢ, mⱼ),

wobei ggT den größten gemeinsamen Teiler bezeichnet. Falls diese Bedingung erfüllt ist, sind alle Lösungen kongruent modulo dem kgV der Moduln. Eine Lösung kann beispielsweise durch sukzessive Substitution gefunden werden.

Im klassischen Rätsel wird die kleinste positive Zahl gesucht, die bei Division durch 2, 3, 4, 5 und 6 jeweils den Rest 1 lässt und durch 7 teilbar ist. Die ersten fünf Bedingungen lassen sich zusammenfassen, weil kgV(2, 3, 4, 5, 6) = 60 gilt:

x ≡ 1 mod 60, x ≡ 0 mod 7.

Dieses nun vereinfachte System ist mit dem chinesischen Restsatz lösbar. Seine Lösungen sind kongruent zu 301 modulo 420.

Direktes Lösen von zwei Kongruenzen

Für die beiden Kongruenzen

x ≡ a mod n, x ≡ b mod m

gilt bei Lösbarkeit, also bei a ≡ b mod d, mit d = ggT(n, m) = yn + zm, die äquivalente einfache Kongruenz

x ≡ a − yn(a − b)/d mod (nm/d).

Das Verfahren funktioniert auch für nicht teilerfremde Zahlen n und m. Ein System mit mehreren Kongruenzen kann durch wiederholte Anwendung dieser Vereinfachung gelöst werden.

Formulierung für Ringe

Für einen Hauptidealring R gilt: Sind m₁, …, mₙ paarweise teilerfremd und ist m ihr Produkt, dann ist der Faktorring R/mR isomorph zum Produktring R/m₁R × ⋯ × R/mₙR. Der Isomorphismus lautet

x + mR ↦ (x + m₁R, …, x + mₙR).

Die allgemeinste angegebene Form gilt für einen beliebigen Ring R mit Einselement. Sind I₁, …, Iₙ zweiseitige Ideale mit Iᵢ + Iⱼ = R für i ≠ j, nennt man sie teilerfremd oder coprim. Für ihren Durchschnitt I gilt:

R/I ≅ R/I₁ × ⋯ × R/Iₙ,

wobei der Isomorphismus x + I ↦ (x + I₁, …, x + Iₙ) verwendet. Ist R kommutativ, ist I außerdem gleich dem Produkt der Ideale Iⱼ.

Für den Beweis ist die Abbildung zunächst ein Ringhomomorphismus. Man zeigt ihre Isomorphie durch Lokalisierung an allen Primidealen und kann dadurch einen lokalen Ring mit genau einem maximalen Ideal betrachten. In einem solchen Ring können höchstens eines der Ideale Iᵢ echt sein; sind alle gleich R, ist die Aussage unmittelbar. Ist beispielsweise nur I₁ echt, dann gilt I = I₁ · R · ⋯ · R = I₁, und beide Seiten reduzieren sich auf R/I₁ beziehungsweise auf R/I₁ × {0} × ⋯ × {0}. Diese Ringe sind isomorph.