Logo

Mathepedia

Unterstützen Sie die Mathepedia!

Jetzt

Mathepedia auf Facebook

Wurzelzieher Blog

Elementare Zahlentheorie


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
wFormel
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 wFormel 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:
wFormel für i = 1, ..., n
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
wFormel.
Setzen wir wFormel, dann gilt
wFormel
wFormel.
Die Zahl
wFormel
ist dann eine Lösung der simultanen Kongruenz.

Beispiel

Gesucht sei eine ganze Zahl x mit der Eigenschaft
wFormel
Hier ist wFormel.
Mit Hilfe des erweiterten Euklidischen Algorithmus berechnet man
wFormel, also e1 = 40
wFormel, also e2 = 45
wFormel, also e3 = - 24
Eine Lösung ist dann wFormel. Wegen wFormel 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 wFormel gilt:
wFormel.
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
wFormel
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 wFormel, d.h. zu finden ist eine Lösung von
wFormel
Dieses Kongruenzsystem ist nun mit dem Chinesischen Restsatz lösbar. (Die Lösung sei dem Leser überlassen.)

Die Furcht vor der Mathematik steht der Angst erheblich näher als der Ehrfurcht.

Felix Auerbach

 

 

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.



Anbieterkеnnzeichnung: Wurzelzieher Mathеpеdιa  •  Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
 
G: 23.01.2014 11:05:05 (1.253 ms; 235 M)
C: 25.07.2014 22:35:09 (32 ms; 261 M)