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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{matrix} x & \equiv & a_1 & \pmod{m_1} \\ x & \equiv & a_2 & \pmod{m_2} \\ & \vdots & & \\ x & \equiv & a_n & \pmod{m_n} \\ \end{matrix} }

für die alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} bestimmt werden sollen, die sämtliche Kongruenzen gleichzeitig lösen. Wenn eine Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0} existiert, dann sind mit $M:=\operatorname {kgV} (m_{1},m_{2},m_{3},\ldots ,m_{n})$ die Zahlen Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle x_{0}+kM\ (k\in \mathbb {Z} )} genau alle Lösungen, wobei Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \operatorname {kgV} } 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 (chinesisch 

孫子算經

 / 

孙子算经

 – „Sun Zis Handbuch der Arithmetik“) des Mathematikers Sun Zi (vermutlich 3. Jh.) 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle m_{1},\ldots ,m_{n}} paarweise teilerfremde natürliche Zahlen, dann existiert für jedes Tupel ganzer Zahlen Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle a_{1},\ldots ,a_{n}} eine ganze Zahl $x$, die die folgende simultane Kongruenz erfüllt:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle x\equiv a_{i}\mod m_{i}} für $i=1,\ldots ,n$

Alle Lösungen dieser Kongruenz sind kongruent modulo $M:=m_{1}m_{2}m_{3}\ldots m_{n}$.

Das Produkt $M$ stimmt hier wegen der Teilerfremdheit mit dem Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \operatorname {kgV} } überein.

Finden einer Lösung

Eine Lösung $x$ kann wie folgt ermittelt werden: Für jedes $i$ sind die Zahlen $m_{i}$ und $M_{i}:=M/m_{i}$ teilerfremd, also kann man z. B. mit dem erweiterten euklidischen Algorithmus zwei ganze Zahlen Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle r_{i}} und $s_{i}$ finden, so dass

$r_{i}\cdot m_{i}+s_{i}\cdot M_{i}=1$.

Setze $e_{i}:=s_{i}\cdot M_{i}$, dann gilt

$e_{i}\equiv 1\mod m_{i}$

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle e_{i}\equiv 0\mod m_{j},\ j\neq i} .

Die Zahl

$x:=\sum _{i=1}^{n}a_{i}e_{i}$

ist dann eine Lösung der simultanen Kongruenz.

Beispiel

Gesucht sei eine ganze Zahl $x$ mit der Eigenschaft

${\begin{matrix}x&\equiv &2&{\pmod {3}}\\x&\equiv &3&{\pmod {4}}\\x&\equiv &2&{\pmod {5}}\\\end{matrix}}$

Hier ist $M=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

$7\cdot 3+(-1)\cdot 20=1$, also $e_{1}=-20$

$4\cdot 4+(-1)\cdot 15=1$, also $e_{2}=-15$

$5\cdot 5+(-2)\cdot 12=1$, also $e_{3}=-24$

Eine Lösung ist dann $x=2\cdot (-20)+3\cdot (-15)+2\cdot (-24)=-133$. Wegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -133 \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\neq j$ gilt:

$a_{i}\equiv a_{j}\mod {}\operatorname {ggT} (m_{i},m_{j})$,

wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{ggT}(m_i, m_j)} für den größten gemeinsamen Teiler von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_i} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_j} steht. Alle Lösungen sind dann kongruent modulo dem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{kgV}} der $m_{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 $x$ der simultanen Kongruenz

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{matrix} 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 \\ \end{matrix} }

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \equiv 1 \mod \operatorname{kgV}(2, 3, 4, 5, 6)} , d. h. zu finden ist eine Lösung von

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{matrix} x & \equiv & 1 & \mod 60 \\ x & \equiv & 0 & \mod 7 \\ \end{matrix} }

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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{matrix} x & \equiv & a & \pmod{n} \\ x & \equiv & b & \pmod{m} \\ \end{matrix} }

Wenn diese lösbar sind, das heißt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \equiv b \pmod d} , so sind sie äquivalent mit der einfachen Kongruenz:

${\begin{matrix}x&\equiv &a-yn{\frac {a-b}{d}}&{\pmod {\frac {nm}{d}}}\\\end{matrix}}$

mit

$d=\operatorname {ggT} (n,m)=yn+zm$.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} ein Hauptidealring, dann lautet der chinesische Restsatz für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} wie folgt:

Sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_1, \ldots, m_n} paarweise teilerfremd und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} ihr Produkt, dann ist der Faktorring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R/mR} isomorph zum Produktring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R/m_1 R \times \cdots \times R/m_n R} durch den Isomorphismus

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{matrix} f : & R/mR & \to & R/m_1R \times \cdots \times R/m_nR \\ & x + mR & \mapsto & (x + m_1R, \ldots, x + m_nR) \end{matrix} }

Aussage für allgemeine Ringe

Eine der allgemeinsten Formen des chinesischen Restsatzes ist eine Formulierung für einen beliebigen Ring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} (mit Einselement).

Sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I_1, \ldots, I_n} (beidseitige) Ideale, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I_i + I_j = R} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \neq j} (man nennt die Ideale dann teilerfremd oder koprim), und sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I} der Durchschnitt der Ideale, dann ist der Faktorring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R/I} isomorph zum Produktring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R/I_1 \times \cdots \times R/I_n} durch den Isomorphismus

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{matrix} f : & R/I & \to & R/I_1 \times \cdots \times R/I_n \\ & x + I & \mapsto & (x + I_1, \ldots, x + I_n). \end{matrix} }

(Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I} ist auch gleich dem Produkt der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I_j} , falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} ein kommutativer Ring ist.)

Weblinks

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

• Programm zur Berechnung simultaner Kongruenzen
• Chinese Remainder Theorem in der Encyclopaedia of Mathematics
• Eric W. Weisstein: Chinese Remainder Theorem. In: MathWorld (englisch).
• Christian Spannagel: Chinesischer Restsatz. Vorlesungsreihe, 2012.
• Chinese Remainder Theorem. Planetmath.org (englisch).