Infos Home | Impressum | Original Artikel & Autoren Liste

Chinesischer Restsatz

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

Inhalt
1 Simultane Kongruenzen ganzer Zahlen
2 Aussage für Hauptidealringe
3 Aussage für allgemeine Ringe

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(m1, m2, m3, ..., mn) 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 m1, ..., mn paarweise teilerfremde positive ganze Zahlen, dann existiert für jedes Tupel ganzer Zahlen a1, ..., an eine ganze Zahl x, die die folgende simultane Kongruenz erfüllt:''

x ≡ ai mod mi für i = 1,...,n
Alle Lösungen dieser Kongruenz sind kongruent modulo M:=m1m2m3...mn.

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 mi und Mi:=M/mi teilerfremd, also kann man z.B. mit dem erweiterten Euklidischen Algorithmus zwei Zahlen r und s finden, so dass

r·mi + s·Mi = 1.

Setzen wir ei:=s·Mi, dann gilt
ei ≡ 1 mod mi
ei ≡ 0 mod mj, 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, M1 = M/3 = 20, M2 = M/4 = 15, M3 = M/5 = 12. Mit Hilfe des erweiterten Euklidischen Algorithmus berechnet man
(-13) · 3 + 2 · 20 = 1, also e1 = 40
(-11) · 4 + 3 · 15 = 1, also e2 = 45
5 · 5 + (-2) · 12 = 1, also e3 = -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:
ai ≡ aj mod ggT(mi, mj).
Alle Lösungen sind dann kongruent modulo dem kgV der mi.

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 m1, ..., mn paarweise teilerfremd und m ihr Produkt, dann ist der Faktorring R/mR isomorph zum Produktring R/m1R × ... × R/mnR durch den Isomorphismus

Aussage für allgemeine Ringe

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

Sind I1, ..., In (beidseitige) Ideale, so dass Ii + Ij = 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 Ij und der Faktorring R/I ist isomorph zum Produktring R/I1 × ... × R/In durch den Isomorphismus


Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz.