Chinesischer Restsatz ist der Name mehrerer ähnlicher Theoreme der abstrakten Algebra und Zahlentheorie.

Simultane Kongruenzen ganzer Zahlen

Eine simultane Kongruenz ganzer Zahlen ist ein System von linearen Kongruenzen

für die alle x bestimmt werden sollen, die sämtliche Kongruenzen gleichzeitig lösen. Wenn eine Lösung x existiert, dann sind mit M := kgV(m₁, m₂, m₃, ..., m_n) die Zahlen x+kM (k in Z) genau alle Lösungen. Es kann aber auch sein, dass es gar keine Lösung gibt.

Teilerfremde Moduln

Die Originalform des Chinesischen Restsatzes aus einem Buch des chinesischen Mathematikers Ch'in Chiu-Shao aus dem Jahr 1247 ist eine Aussage über simultane Kongruenzen für den Fall, dass die Moduln teilerfremd sind. Sie lautet:

Seien m₁, ..., m_n paarweise teilerfremde positive ganze Zahlen, dann existiert für jedes Tupel ganzer Zahlen a₁, ..., a_n eine ganze Zahl x, die die folgende simultane Kongruenz erfüllt:

x ? a_i mod m_i für i = 1,...,n

Alle Lösungen dieser Kongruenz sind kongruent modulo M:=m₁m₂m₃...m_n.

Das Produkt M stimmt hier wegen der Teilerfremdheit mit dem kgV überein.

Finden einer Lösung

Eine Lösung x kann man wie folgt ermitteln. Für jedes i sind die Zahlen m_i und M_i:=M/m_i teilerfremd, also kann man z.B. mit dem erweiterten Euklidischen Algorithmus zwei Zahlen r und s finden, so dass

r·m_i + s·M_i = 1.

Setzen wir e_i:=s·M_i, dann gilt

e_i ? 1 mod m_i

e_i ? 0 mod m_j, j ? i.

Die Zahl

ist dann eine Lösung der simultanen Kongruenz.

Beispiel

Gesucht sei eine ganze Zahl x mit der Eigenschaft

x ? 2 (mod 3)

x ? 3 (mod 4)

x ? 2 (mod 5)

Hier ist M = 3 · 4 · 5 = 60, M₁ = M/3 = 20, M₂ = M/4 = 15, M₃ = M/5 = 12. Mit Hilfe des erweiterten Euklidischen Algorithmus berechnet man

(-13) · 3 + 2 · 20 = 1, also e₁ = 40

(-11) · 4 + 3 · 15 = 1, also e₂ = 45

5 · 5 + (-2) · 12 = 1, also e₃ = -24

Eine Lösung ist dann x = 2 × 40 + 3 × 45 + 2 × (-24) = 167. Wegen 167 ? 47 mod 60 sind alle anderen Lösungen also kongruent zu 47 modulo 60.

Allgemeiner Fall

Auch im Fall, dass die Moduln nicht teilerfremd sind, existiert manchmal eine Lösung. Die genaue Bedingung lautet: Eine Lösung der simultanen Kongruenz existiert genau dann, wenn für alle i ? j gilt:

a_i ? a_j mod ggT(m_i, m_j).

Alle Lösungen sind dann kongruent modulo dem kgV der m_i.

Eine simultane Kongruenz lässt sich im Falle der Existenz einer Lösung z.B. durch sukzessive Substitution lösen, auch wenn die Moduln nicht teilerfremd sind.

Beispiel

Ein klassisches Rätsel besteht darin, die kleinste natürliche Zahl zu finden, die bei Division durch 2, 3, 4, 5 und 6 jeweils den Rest 1 lässt, und durch 7 teilbar ist. Gesucht ist also die kleinste positive Lösung x der simultanen Kongruenz

x ? 1 mod 2

x ? 1 mod 3

x ? 1 mod 4

x ? 1 mod 5

x ? 1 mod 6

x ? 0 mod 7

Da die Moduln nicht teilerfremd sind, kann man nicht direkt den Chinesischen Restsatz (mit Lösungsverfahren) anwenden. Man kann aber die ersten fünf Bedingungen zusammenfassen zu x ? 1 mod kgV(2, 3, 4, 5, 6), d.h. zu finden ist eine Lösung von

x ? 1 mod 60

x ? 0 mod 7.

Dieses Kongruenzsystem ist nun mit dem Chinesischen Restsatz lösbar. (Die Lösung sei dem Leser überlassen.)

Aussage für Hauptidealringe

Sei R ein Hauptidealring, dann lautet der Chinesische Restsatz für R so:

Sind m₁, ..., m_n paarweise teilerfremd und m ihr Produkt, dann ist der Faktorring R/mR isomorph zum Produktring R/m₁R × ... × R/m_nR durch den Isomorphismus

Aussage für allgemeine Ringe

Eine der allgemeinsten Formen des Chinesischen Restsatzes ist eine Formulierung für einen beliebigen Ring R.

Sind I₁, ..., I_n (beidseitige) Ideale, so dass I_i + I_j = R für i ? j (man nennt die Ideale dann teilerfremd), und sei I das Produkt der Ideale, dann ist I gleich dem Durchschnitt der I_j und der Faktorring R/I ist isomorph zum Produktring R/I₁ × ... × R/I_n durch den Isomorphismus