Chinesischer Restsatz

mathematischer Satz

Chinesischer Restsatz (auch chinesischer Restklassensatz genannt) ist der Name mehrerer ähnlicher Theoreme der abstrakten Algebra und Zahlentheorie.

Simultane Kongruenzen ganzer ZahlenBearbeiten

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   kgV  die Zahlen   genau alle Lösungen. Es kann aber auch sein, dass es gar keine Lösung gibt.

Teilerfremde ModulnBearbeiten

HerleitungBearbeiten

Die Originalform des chinesischen Restsatzes stammt aus dem Buch Sūn Zǐ Suànjīng (chinesisch 孫子算經 / 孙子算经 – „Sun Zis Handbuch der Arithmetik“) des 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:

Seien   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 kgV überein.

Finden einer LösungBearbeiten

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.

BeispielBearbeiten

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 FallBearbeiten

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:

  ggT .

Alle Lösungen sind dann kongruent modulo dem kgV 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.

BeispielBearbeiten

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 ZahlenBearbeiten

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 HauptidealringeBearbeiten

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 RingeBearbeiten

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.)

WeblinksBearbeiten

Wikibooks: Beweis des Satzes im Beweisarchiv – Lern- und Lehrmaterialien

EinzelnachweiseBearbeiten

  1. J. J. O’Connor, E. F. Robertson: Sun Zi biography. School of Mathematics and Statistics, University of St Andrews, Scotland, abgerufen am 5. August 2010 (englisch).
  2. H. Gericke gibt als möglichen Entstehungszeitraum 280 bis 473 n. Chr. an. (H. Gericke: Mathematik in Antike, Orient und Abendland. Springer, Berlin 1990, Abschnitt 3.1, S. 182)
  3. Einen Beweis dafür, dass diese Bedingung hinreichend ist, findet man bei A. Bogomolny: Chinese Remainder Theorem, Theorem 2 auf Interactive Mathematics Miscellany and Puzzles (englisch); die Notwendigkeit ist leicht zu sehen.