# 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 coprim), 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.)
Diese Aussage lässt sich wie folgt beweisen: $f$ ist ein Ringhomomorphismus und $f$ ist genau dann ein Isomorphismus, wenn $f\otimes _{R}\operatorname {id} _{R_{\mathfrak {p}}}$ein Isomorphismus ist für alle Primideale ${\mathfrak {p}}\subseteq R$. Da Lokalisierung mit Durchschnitt und Quotientenbildung verträglich ist, kann man ohne Einschränkung annehmen, dass ${\ce {R}}$ ein lokaler Ring ist mit einzigem maximalen Ideal ${\mathfrak {m}}$. Wenn $I_{i}\subseteq {\mathfrak {m}}$ und $I_{j}\subseteq {\mathfrak {m}}$, dann ist auch $I_{i}+I_{j}\subseteq m\subsetneq R$. Da jedes Ideal ungleich $R$ in dem maximalen Ideal ${\mathfrak {m}}$ enthalten sein muss, ist $I_{i}\neq R$ für höchstens ein $i$. Wenn alle $I_{i}$ gleich dem ganzen Ring $R$ sind, dann ist die Aussage wahr, denn dann ist $f\colon \{0\}\to \prod _{i=1}^{n}\{0\}\cong \{0\}$ ein Isomorphismus. Sei also ohne Einschränkung $I_{1}$ das einzige Ideal $I_{i}$, sodass $I_{i}\neq R$.
Es ist $I_{1}\cdots I_{r}=I_{1}\cdot R\cdots R=I_{1}=I$ und außerdem
$R/I=R/I_{1}\cong R/I_{1}\times \{0\}\times \dots \times \{0\}=R/I_{i}\times R/R\times \dots \times R/R\cong \prod _{i=1}^{n}R/I_{i}$