Chinesischer Restsatz
Chinesischer Restsatz (auch chinesischer Restklassensatz genannt) 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 bestimmt werden sollen, die sämtliche Kongruenzen gleichzeitig lösen. Wenn eine Lösung
existiert, dann sind mit
die Zahlen
genau alle Lösungen, wobei
für das kleinste gemeinsame Vielfache steht. Es kann aber auch sein, dass es gar keine Lösung gibt.
Teilerfremde Moduln
Herleitung
Die Originalform des chinesischen Restsatzes stammt aus dem Buch Sūn Zǐ Suànjīng (chinesisch 孫子算經 / 孙子算经 – „Sun Zis Handbuch der Arithmetik“) des chinesischen Mathematikers Sun Zi (vermutlich 3. Jh.[1][2]) und wurde 1247 von Qin Jiushaos Shùshū Jiǔzhāng (數書九章 / 数书九章 – „Mathematische Abhandlung in neun Kapiteln“) wiederveröffentlicht. Der Satz trifft eine Aussage über simultane Kongruenzen für den Fall, dass die Moduln teilerfremd sind. Sie lautet:
Sind paarweise teilerfremde natürliche Zahlen, dann existiert für jedes Tupel ganzer Zahlen
eine ganze Zahl
, die die folgende simultane Kongruenz erfüllt:
für
Alle Lösungen dieser Kongruenz sind kongruent modulo .
Das Produkt stimmt hier wegen der Teilerfremdheit mit dem
überein.
Finden einer Lösung
Eine Lösung kann wie folgt ermittelt werden: Für jedes
sind die Zahlen
und
teilerfremd, also kann man z. B. mit dem erweiterten euklidischen Algorithmus zwei ganze Zahlen
und
finden, so dass:
.
Setze , dann gilt:
.
Die Zahl
ist dann eine Lösung der simultanen Kongruenz.
Beispiel
Gesucht sei eine ganze Zahl mit der Eigenschaft
Hier ist .Mit Hilfe des erweiterten euklidischen Algorithmus berechnet man
, also
, also
, also
Eine Lösung ist dann . Wegen
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[3] lautet:Eine Lösung der simultanen Kongruenz existiert genau dann, wenn für alle gilt:
,
wobei für den größten gemeinsamen Teiler von
und
steht.Alle Lösungen sind dann kongruent modulo dem
der
.
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 der simultanen Kongruenz
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 , d. h. zu finden ist eine Lösung von
Dieses Kongruenzsystem ist nun mit dem chinesischen Restsatz lösbar. Die Lösungen sind kongruent zu 301 modulo 420.
Direktes Lösen von simultanen Kongruenzen ganzer Zahlen
Gegeben sind die beiden simultanen Kongruenzen:
Wenn diese lösbar sind, das heißt , so sind sie äquivalent mit der einfachen Kongruenz:
mit
.
Dieses funktioniert auch mit nicht teilerfremden Zahlen n und m und stellt somit eine deutliche Erleichterung bei dem Lösen von simultanen Kongruenzen dar.
Ein System aus Kongruenzen lässt sich durch wiederholtes Anwenden dieser Vereinfachung lösen.
Aussage für Hauptidealringe
Sei ein Hauptidealring, dann lautet der chinesische Restsatz für
wie folgt:
Sind paarweise teilerfremd und
ihr Produkt, dann ist der Faktorring
isomorph zum Produktring
durch den Isomorphismus
Aussage für allgemeine Ringe
Eine der allgemeinsten Formen des chinesischen Restsatzes ist eine Formulierung für einen beliebigen Ring (mit Einselement).
Sind (beidseitige) Ideale, so dass
für
(man nennt die Ideale dann teilerfremd oder koprim), und sei
der Durchschnitt der Ideale, dann ist der Faktorring
isomorph zum Produktring
durch den Isomorphismus
( ist auch gleich dem Produkt der
, falls
ein kommutativer Ring ist.)
Weblinks
- Programm zur Berechnung simultaner Kongruenzen
- Chinese Remainder Theorem in der Encyclopaedia of Mathematics
- Eric W. Weisstein: Chinese Remainder Theorem. In: MathWorld (englisch).
- Christian Spannagel: Chinesischer Restsatz. Vorlesungsreihe, 2012.
- Chinese Remainder Theorem. Planetmath.org (englisch).