Chinesischer Restsatz
# 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

    ${\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 $x$ bestimmt werden sollen, die sämtliche Kongruenzen gleichzeitig lösen. Wenn eine Lösung $x_{0}$ existiert, dann sind mit $M:=\operatorname {kgV} (m_{1},m_{2},m_{3},\ldots ,m_{n})$ die Zahlen $x_{0}+kM\ (k\in \mathbb {Z} )$ genau alle Lösungen, wobei $\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 chinesischen 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:

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

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

    ${\begin{aligned}e_{i}&\equiv 1{\pmod {m_{i}}}\\e_{i}&\equiv 0{\pmod {m_{j}}},\ j\neq i\end{aligned}}$.

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 $-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 $\operatorname {ggT} (m_{i},m_{j})$ für den größten gemeinsamen Teiler von $m_{i}$ und $m_{j}$ steht. Alle Lösungen sind dann kongruent modulo dem $\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

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

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

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

Wenn diese lösbar sind, das heißt $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 $R$ ein Hauptidealring, dann lautet der chinesische Restsatz für $R$ wie folgt:

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

    ${\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 $R$ (mit Einselement).

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

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

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

