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 () des chinesischen Mathematikers Sun Zi (vermutlich 3. Jh.) und wurde 1247 von Qin Jiushaos Shùshū Jiǔzhāng () 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 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
 
 Christian Spannagel: Chinesischer Restsatz. Vorlesungsreihe, 2012.
 Chinese Remainder Theorem. Planetmath.org (englisch).

Einzelnachweise 

Satz (Zahlentheorie)
Algebra