Elementare Zahlentheorie
-
Kongruenzen
Veranschaulichung
-
Satz von Fermat
Chinesischer Restsatz
Chinesischer Restsatz 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 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 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 ganze Zahlen, dann existiert für jedes Tupel ganzer Zahlen a1 , ..., an eine ganze Zahl x, die die folgende simultane Kongruenz erfüllt:
Alle Lösungen dieser Kongruenz sind kongruent modulo M := m1 m2 m3 ...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 ri und si finden, so dass
Setzen wir , dann gilt
Die Zahl
ist dann eine Lösung der simultanen Kongruenz.
Beispiel
Gesucht sei eine ganze Zahl x mit der Eigenschaft
Hier ist .
Mit Hilfe des erweiterten Euklidischen Algorithmus berechnet man
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:
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
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ösung sei dem Leser überlassen.)
Insofern sich die Sätze der Mathematik auf die Wirklichkeit beziehen, sind sie nicht sicher, und insofern sie sicher sind, beziehen sie sich nicht auf die Wirklichkeit.
Albert Einstein
Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Chinesischer Restsatz aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Lizеnz Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). Listе dеr Autorеn des Originalartikels. Achtung! Unter Umständen besitzt diese Seite kaum noch Ähnlichkeit mit dem genannten Wιkιpеdιa-Artikel, da dieser komplett überarbeitet werdet musste, um Fehler und irrelevante Informationen zu entfernen.