Chinesischer Restsatz
Chinesischer Restsatz ist der Name mehrerer ähnlicher Theoreme der abstrakten Algebra und Zahlentheorie.
Table of contents |
2 Aussage für Hauptidealringe 3 Aussage für allgemeine Ringe |
Eine simultane Kongruenz ganzer Zahlen ist ein System von linearen Kongruenzen
Simultane Kongruenzen ganzer Zahlen
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.
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:''
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
Beispiel
Gesucht sei eine ganze Zahl x mit der Eigenschaft
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:
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
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
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
Teilerfremde Moduln
Alle Lösungen dieser Kongruenz sind kongruent modulo M:=m1m2m3...mn.
Setzen wir ei:=s·Mi, dann gilt
Die Zahl
ist dann eine Lösung der simultanen Kongruenz.
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
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
Alle Lösungen sind dann kongruent modulo dem kgV der mi.
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
Dieses Kongruenzsystem ist nun mit dem Chinesischen Restsatz lösbar. (Die Lösung sei dem Leser überlassen.)Aussage für Hauptidealringe
Aussage für allgemeine Ringe