Chinesischer Restsatz

Chinesischer Restsatz (auch chinesischer Restklassensatz genannt) i​st der Name mehrerer ähnlicher Theoreme d​er abstrakten Algebra u​nd Zahlentheorie.

Simultane Kongruenzen ganzer Zahlen

Eine simultane Kongruenz ganzer Zahlen i​st ein System v​on linearen Kongruenzen

${\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 ${\displaystyle x}$ bestimmt werden sollen, die sämtliche Kongruenzen gleichzeitig lösen. Wenn eine Lösung ${\displaystyle x_{0}}$ existiert, dann sind mit ${\displaystyle M:=\operatorname {kgV} (m_{1},m_{2},m_{3},\ldots ,m_{n})}$ die Zahlen ${\displaystyle x_{0}+kM\ (k\in \mathbb {Z} )}$ genau alle Lösungen, wobei ${\displaystyle \operatorname {kgV} }$ für das kleinste gemeinsame Vielfache steht. Es kann aber auch sein, dass es gar keine Lösung gibt.

Herleitung

Die Originalform d​es chinesischen Restsatzes stammt a​us dem Buch Sūn Zǐ Suànjīng (chinesisch 孫子算經 / 孙子算经 – „Sun Zis Handbuch d​er Arithmetik“) d​es Mathematikers Sun Zi (vermutlich 3. Jh.[1][2]) u​nd wurde 1247 v​on Qin Jiushaos Shùshū Jiǔzhāng (數書九章 / 数书九章 – „Mathematische Abhandlung i​n neun Kapiteln“) wiederveröffentlicht. Der Satz trifft e​ine Aussage über simultane Kongruenzen für d​en Fall, d​ass die Moduln teilerfremd sind. Sie lautet:

Seien ${\displaystyle m_{1},\ldots ,m_{n}}$ paarweise teilerfremde natürliche Zahlen, dann existiert für jedes Tupel ganzer Zahlen ${\displaystyle a_{1},\ldots ,a_{n}}$ eine ganze Zahl ${\displaystyle x}$, die die folgende simultane Kongruenz erfüllt:

${\displaystyle x\equiv a_{i}\mod m_{i}}$ für ${\displaystyle i=1,\ldots ,n}$

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

Das Produkt ${\displaystyle M}$ stimmt hier wegen der Teilerfremdheit mit dem ${\displaystyle \operatorname {kgV} }$ überein.

Finden einer Lösung

Eine Lösung ${\displaystyle x}$ kann wie folgt ermittelt werden: Für jedes ${\displaystyle i}$ sind die Zahlen ${\displaystyle m_{i}}$ und ${\displaystyle M_{i}:=M/m_{i}}$ teilerfremd, also kann man z. B. mit dem erweiterten euklidischen Algorithmus zwei ganze Zahlen ${\displaystyle r_{i}}$ und ${\displaystyle s_{i}}$ finden, so dass

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

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

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

${\displaystyle e_{i}\equiv 0\mod m_{j},\ j\neq i}$.

Die Zahl

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

ist d​ann eine Lösung d​er simultanen Kongruenz.

Beispiel

Gesucht sei eine ganze Zahl ${\displaystyle x}$ mit der Eigenschaft

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

Hier ist ${\displaystyle 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

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

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

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

Eine Lösung ist dann ${\displaystyle x=2\cdot (-20)+3\cdot (-15)+2\cdot (-24)=-133}$. Wegen ${\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[3] lautet: Eine Lösung der simultanen Kongruenz existiert genau dann, wenn für alle ${\displaystyle i\neq j}$ gilt:

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

wobei ${\displaystyle \operatorname {ggT} (m_{i},m_{j})}$ für den größten gemeinsamen Teiler von ${\displaystyle m_{i}}$ und ${\displaystyle m_{j}}$ steht. Alle Lösungen sind dann kongruent modulo dem ${\displaystyle \operatorname {kgV} }$ der ${\displaystyle m_{i}}$.

Eine simultane Kongruenz lässt s​ich im Falle d​er Existenz e​iner Lösung z. B. d​urch sukzessive Substitution lösen, a​uch wenn d​ie Moduln n​icht 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 ${\displaystyle x}$ der simultanen Kongruenz

${\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 ${\displaystyle x\equiv 1\mod \operatorname {kgV} (2,3,4,5,6)}$, d. h. zu finden ist eine Lösung von

${\displaystyle {\begin{matrix}x&\equiv &1&\mod 60\\x&\equiv &0&\mod 7\\\end{matrix}}}$

Dieses Kongruenzsystem i​st nun m​it dem chinesischen Restsatz lösbar. Die Lösungen s​ind kongruent z​u 301 modulo 420.

Direktes Lösen von simultanen Kongruenzen ganzer Zahlen

Gegeben s​ind die beiden simultanen Kongruenzen:

${\displaystyle {\begin{matrix}x&\equiv &a&{\pmod {n}}\\x&\equiv &b&{\pmod {m}}\\\end{matrix}}}$

Wenn diese lösbar sind, das heißt ${\displaystyle a\equiv b{\pmod {d}}}$, so sind sie äquivalent mit der einfachen Kongruenz:

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

mit

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

Dieses funktioniert a​uch mit n​icht teilerfremden Zahlen n u​nd m u​nd stellt s​omit eine deutliche Erleichterung b​ei dem Lösen v​on simultanen Kongruenzen dar.

Ein System a​us Kongruenzen lässt s​ich durch wiederholtes Anwenden dieser Vereinfachung lösen.

Aussage für Hauptidealringe

Sei ${\displaystyle R}$ ein Hauptidealring, dann lautet der chinesische Restsatz für ${\displaystyle R}$ wie folgt:

Sind ${\displaystyle m_{1},\ldots ,m_{n}}$ paarweise teilerfremd und ${\displaystyle m}$ ihr Produkt, dann ist der Faktorring ${\displaystyle R/mR}$ isomorph zum Produktring ${\displaystyle R/m_{1}R\times \cdots \times R/m_{n}R}$ durch den Isomorphismus

${\displaystyle {\begin{matrix}f:&R/mR&\to &R/m_{1}R\times \cdots \times R/m_{n}R\\&x+mR&\mapsto &(x+m_{1}R,\ldots ,x+m_{n}R)\end{matrix}}}$

Aussage für allgemeine Ringe

Eine der allgemeinsten Formen des chinesischen Restsatzes ist eine Formulierung für einen beliebigen Ring ${\displaystyle R}$ (mit Einselement).

Sind ${\displaystyle I_{1},\ldots ,I_{n}}$ (beidseitige) Ideale, so dass ${\displaystyle I_{i}+I_{j}=R}$ für ${\displaystyle i\neq j}$ (man nennt die Ideale dann teilerfremd oder koprim), und sei ${\displaystyle I}$ der Durchschnitt der Ideale, dann ist der Faktorring ${\displaystyle R/I}$ isomorph zum Produktring ${\displaystyle R/I_{1}\times \cdots \times R/I_{n}}$ durch den Isomorphismus

${\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}}}$

(${\displaystyle I}$ ist auch gleich dem Produkt der ${\displaystyle I_{j}}$, falls ${\displaystyle R}$ ein kommutativer Ring ist.)

Weblinks

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

Einzelnachweise

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.