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
x≡a1mod  m1x≡a2mod  m2 ⋮  x≡anmod  mn \array{ {x \equiv {a_1} {\mod m_1} } \\{x \equiv {a_2} {\mod m_2} }\\ {\, \vdots \, \, } \\{x \equiv {a_n} { \mod m_n} } }
für die alle xx bestimmt werden sollen, die sämtliche Kongruenzen gleichzeitig lösen. Wenn eine Lösung xx existiert, dann sind mit M:=kgV⁡(m1,m2,m3,…,mn)M := \kgV(m_1, m_2, m_3, \ldots, m_n) die Zahlen x+kMx + kM (k∈Z)(k \in \mathbb{Z}) 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,…,mnm_1, \ldots, m_n paarweise teilerfremde ganze Zahlen, dann existiert für jedes Tupel ganzer Zahlen a1,…,ana_1, \ldots, a_n eine ganze Zahl xx, die die folgende simultane Kongruenz erfüllt:
x≡aimod  mix \equiv a_i \mod m_i für i=1,…,ni = 1, \ldots, n
Alle Lösungen dieser Kongruenz sind kongruent modulo M:=m1m2m3…mnM := m_1 m_2 m_3 \ldots m_n.
Das Produkt MM stimmt hier wegen der Teilerfremdheit mit dem kgV überein.

Finden einer Lösung

Eine Lösung xx kann man wie folgt ermitteln. Für jedes ii sind die Zahlen mim_i und Mi:=M/miM_i := M / m_i teilerfremd, also kann man z.B. mit dem erweiterten euklidischen Algorithmus zwei Zahlen rir_i und sis_i finden, so dass
ri⋅mi+si⋅Mi=1r_i \cdot m_i + s_i \cdot M_i = 1.
Setzen wir ei:=si⋅Mie_i := s_i \cdot M_i, dann gilt
ei≡1mod  mie_i \equiv 1 \mod m_i
ei≡0mod  mj, j≠ie_i \equiv 0 \mod m_j, \ j \neq i.
Die Zahl
x:=∑i=1naieix := \sum\limits_{i=1}^n a_i e_i
ist dann eine Lösung der simultanen Kongruenz.

Beispiel

Gesucht sei eine ganze Zahl xx mit der Eigenschaft
x≡2(mod3)x≡3(mod4)x≡2(mod5)\array{ {x \equiv 2 {\pmod 3} } {x \equiv 3 {\pmod 4} } {x \equiv 2 {\pmod 5} } }
Hier ist M=3⋅4⋅5=60, M1=M/3=20, M2=M/4=15, M3=M/5=12M = 3 \cdot 4 \cdot 5 = 60, \ M_1 = M/3 = 20, \ M_2 = M/4 = 15, \ M_3 = M/5 = 12.
Mit Hilfe des erweiterten Euklidischen Algorithmus berechnet man
(−13)⋅3+2⋅20=1(-13) \cdot 3 + 2 \cdot 20 = 1, also e1=40e_1 = 40
(−11)⋅4+3⋅15=1(-11) \cdot 4 + 3 \cdot 15 = 1, also e2=45e_2 = 45
5⋅5+(−2)⋅12=15 \cdot 5 + (-2) \cdot 12 = 1, also e3=−24e_3 = -24
Eine Lösung ist dann x=2⋅40+3⋅45+2⋅(−24)=167x = 2 \cdot 40 + 3 \cdot 45 + 2 \cdot (-24) = 167. Wegen 167≡47mod  60167 \equiv 47 \mod 60 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 i≠ji \neq j gilt:
ai≡ajmod  ggT⁡(mi,mj)a_i \equiv a_j \mod \ggT(m_i, m_j).
Alle Lösungen sind dann kongruent modulo dem kgV der mim_i.
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 xx der simultanen Kongruenz
x≡1mod  2x≡1mod  3x≡1mod  4x≡1mod  5x≡1mod  6x≡0mod  7\array{ {x \equiv 1 \mod 2 } \\{x \equiv 1 \mod 3 } \\{x \equiv 1 \mod 4 } \\{x \equiv 1 \mod 5 } \\{x \equiv 1 \mod 6 }\\ {x \equiv 0 \mod 7 } }
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 x≡1mod  kgV⁡(2,3,4,5,6)x \equiv 1 \mod \kgV(2, 3, 4, 5, 6), d.h. zu finden ist eine Lösung von
x≡1mod  60x≡0mod  7\array{ {x \equiv 1 \mod 60 } \\{x \equiv 0 \mod 7 } }
Dieses Kongruenzsystem ist nun mit dem Chinesischen Restsatz lösbar. (Die Lösung sei dem Leser überlassen.)

Ein Mathematiker ist eine Maschine, die Kaffee in Theoreme verwandelt.

Paul Erdös

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Chinesischer Restsatz aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Elementare Zahlentheorie