imported>Mathze: Die letzte Textänderung von 195.37.234.83 wurde verworfen und die Version 256361361 von Jule Glühwurm wiederhergestellt.

2025-05-30T18:44:07Z

Die letzte Textänderung von 195.37.234.83 wurde verworfen und die Version 256361361 von Jule Glühwurm wiederhergestellt.

Neue Seite

'''Chinesischer Restsatz''' (auch '''chinesischer Restklassensatz''' genannt) ist der Name mehrerer ähnlicher [[Theorem]]e der [[Abstrakte Algebra|abstrakten Algebra]] und [[Zahlentheorie]].

== Simultane Kongruenzen ganzer Zahlen ==

Eine ''[[simultane Kongruenz]]'' ganzer Zahlen ist ein System von linearen [[Kongruenz (Zahlentheorie)|Kongruenzen]]

: <math>
\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}
</math>

für die alle <math>x</math> bestimmt werden sollen, die sämtliche Kongruenzen gleichzeitig lösen. Wenn eine Lösung <math>x_0</math> existiert, dann sind mit <math>M := \operatorname{kgV}(m_1, m_2, m_3, \ldots, m_n)</math> die Zahlen <math>x_0 + kM \ (k \in \mathbb{Z})</math> genau alle Lösungen, wobei <math>\operatorname{kgV}</math> für das [[Kleinstes gemeinsames Vielfaches|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'' ({{zh|t=孫子算經|v=孙子算经|b=Sun Zis Handbuch der Arithmetik}}) des chinesischen Mathematikers [[Sun Zi (Mathematiker)|Sun Zi]] (vermutlich 3. Jh.)<ref>{{Internetquelle |autor=J. J. O’Connor, E. F. Robertson |url=http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html |titel=Sun Zi biography |hrsg=School of Mathematics and Statistics, University of St Andrews, Scotland |sprache=en |abruf=2010-08-05}}</ref><ref>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)</ref> und wurde 1247 von [[Qin Jiushao]]s ''[[Shushu Jiuzhang|Shùshū Jiǔzhāng]]'' ({{zh|kurz=1|t=數書九章|v=数书九章|b=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 <math>m_1, \ldots, m_n</math> paarweise [[teilerfremd]]e [[Natürliche Zahl|natürliche Zahlen]], dann existiert für jedes [[Tupel]] ganzer Zahlen <math>a_1, \ldots, a_n</math> eine ganze Zahl <math>x</math>, die die folgende simultane Kongruenz erfüllt:
: <math>x \equiv a_i \mod m_i</math> für <math>i = 1, \ldots, n</math>
Alle Lösungen dieser Kongruenz sind kongruent modulo <math>M := m_1 m_2 m_3 \ldots m_n</math>.

Das Produkt <math>M</math> stimmt hier wegen der Teilerfremdheit mit dem <math>\operatorname{kgV}</math> überein.

==== Finden einer Lösung ====
Eine Lösung <math>x</math> kann wie folgt ermittelt werden: Für jedes <math>i</math> sind die Zahlen <math>m_i</math> und <math>M_i := M / m_i</math> teilerfremd, also kann man z. B. mit dem [[Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus]] zwei ganze Zahlen <math>r_i</math> und <math>s_i</math> finden, so dass:
: <math>r_i \cdot m_i + s_i \cdot M_i = 1</math>.

Setze <math>e_i := s_i \cdot M_i</math>, dann gilt:
:<math>
\begin{align}
e_i &\equiv 1 \pmod{m_i} \\
e_i &\equiv 0 \pmod{m_j}, \ j \neq i
\end{align}
</math>.

Die Zahl
: <math>x := \sum_{i=1}^n a_i e_i</math>
ist dann eine Lösung der simultanen Kongruenz.

==== Beispiel ====
Gesucht sei eine ganze Zahl <math>x</math> mit der Eigenschaft
: <math>
\begin{matrix}
x & \equiv & 2 & \pmod 3 \\
x & \equiv & 3 & \pmod 4 \\
x & \equiv & 2 & \pmod 5 \\
\end{matrix}
</math>

Hier ist <math>M = 3 \cdot 4 \cdot 5 = 60, \ M_1 = M/3 = 20, \ M_2 = M/4 = 15, \ M_3 = M/5 = 12</math>.
Mit Hilfe des [[Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus]] berechnet man
: <math>7 \cdot 3 + (-1) \cdot 20 = 1</math>, also <math>e_1 = -20</math>
: <math>4 \cdot 4 + (-1) \cdot 15 = 1</math>, also <math>e_2 = -15</math>
: <math> 5 \cdot 5 + (-2) \cdot 12 = 1</math>, also <math>e_3 = -24</math>

Eine Lösung ist dann <math>x = 2 \cdot (-20) + 3 \cdot (-15) + 2 \cdot (-24) = -133</math>. Wegen <math>-133 \equiv 47 \mod 60</math> 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<ref>Einen Beweis dafür, dass diese Bedingung hinreichend ist, findet man bei A. Bogomolny: ''Chinese Remainder Theorem'', Theorem 2 auf [http://www.cut-the-knot.org/blue/chinese.shtml Interactive Mathematics Miscellany and Puzzles] (englisch); die Notwendigkeit ist leicht zu sehen.</ref> lautet:
Eine Lösung der simultanen Kongruenz existiert genau dann, wenn für alle <math>i \neq j</math> gilt:
: <math>a_i \equiv a_j \mod{} \operatorname{ggT}(m_i, m_j)</math>,
wobei <math>\operatorname{ggT}(m_i, m_j)</math> für den [[ggT|größten gemeinsamen Teiler]] von <math>m_i</math> und <math>m_j</math> steht.
Alle Lösungen sind dann kongruent modulo dem <math>\operatorname{kgV}</math> der <math>m_i</math>.

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 [[Eieraufgabe des Brahmagupta|klassisches Rätsel]] besteht darin, die kleinste natürliche Zahl zu finden, die bei Division durch 2, 3, 4, 5 und 6 jeweils den [[Division mit Rest|Rest]] 1 lässt, und durch 7 [[Teilbarkeit|teilbar]] ist. Gesucht ist also die kleinste positive Lösung <math>x</math> der simultanen Kongruenz
: <math>
\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}
</math>

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 <math>x \equiv 1 \mod \operatorname{kgV}(2, 3, 4, 5, 6)</math>, d. h. zu finden ist eine Lösung von
: <math>
\begin{matrix}
x & \equiv & 1 & \mod 60 \\
x & \equiv & 0 & \mod 7 \\
\end{matrix}
</math>

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:
: <math>
\begin{matrix}
x & \equiv & a & \pmod{n} \\
x & \equiv & b & \pmod{m} \\
\end{matrix}
</math>
Wenn diese lösbar sind, das heißt <math>a \equiv b \pmod d</math>, so sind sie äquivalent mit der einfachen Kongruenz:
: <math>
\begin{matrix}
x & \equiv & a - yn \frac{a-b}{d} & \pmod{ \frac{nm}{d}} \\
\end{matrix}
</math>
mit
:<math>d = \operatorname{ggT}(n,m) = yn + zm</math>.

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 <math>R</math> ein [[Hauptidealring]], dann lautet der chinesische Restsatz für <math>R</math> wie folgt:

Sind <math>m_1, \ldots, m_n</math> paarweise teilerfremd und <math>m</math> ihr Produkt, dann ist der [[Faktorring]] <math>R/mR</math> isomorph zum Produktring <math>R/m_1 R \times \cdots \times R/m_n R</math> durch den [[Isomorphismus]]
: <math>
\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}
</math>

== Aussage für allgemeine Ringe ==

Eine der allgemeinsten Formen des chinesischen Restsatzes ist eine Formulierung für einen beliebigen [[Ring (Algebra)|Ring]] <math>R</math> (mit Einselement).

Sind <math>I_1, \ldots, I_n</math> (beidseitige) [[Ideal (Ringtheorie)|Ideale]], so dass <math>I_i + I_j = R</math> für <math>i \neq j</math> (man nennt die Ideale dann teilerfremd oder coprim), und sei <math>I</math> der Durchschnitt der Ideale, dann ist der Faktorring <math>R/I</math> isomorph zum Produktring
<math>R/I_1 \times \cdots \times R/I_n</math> durch den Isomorphismus
: <math>
\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}
</math>
(<math>I</math> ist auch gleich dem [[Ideal (Ringtheorie)#Konstruktionen|Produkt]] der <math>I_j</math>, falls <math>R</math> ein kommutativer Ring ist.)

Diese Aussage lässt sich wie folgt beweisen: <math>f</math> ist ein Ringhomomorphismus und <math>f</math> ist genau dann ein Isomorphismus, wenn <math>f\otimes_R \operatorname{id}_{R_\mathfrak{p}}</math>ein Isomorphismus ist für alle Primideale <math>\mathfrak p\subseteq R</math>. Da [[Lokalisierung (Algebra)|Lokalisierung]] mit Durchschnitt und Quotientenbildung verträglich ist, kann man ohne Einschränkung annehmen, dass <math>R</math> ein [[lokaler Ring]] ist mit einzigem maximalen Ideal <math>\mathfrak{m}</math>. Wenn <math>I_i\subseteq\mathfrak{m}</math> und <math>I_j\subseteq\mathfrak{m}</math>, dann ist auch <math>I_i+I_j\subseteq m\subsetneq R</math>. Da jedes Ideal ungleich <math>R</math> in dem maximalen Ideal <math>\mathfrak{m}</math> enthalten sein muss, ist <math>I_i\neq R</math> für höchstens ein <math>i</math>. Wenn alle <math>I_i</math> gleich dem ganzen Ring <math>R</math> sind, dann ist die Aussage wahr, denn dann ist <math>f\colon \{0\}\to \prod_{i=1}^n\{0\}\cong\{0\}</math> ein Isomorphismus. Sei also ohne Einschränkung <math>I_1</math> das einzige Ideal <math>I_i</math>, sodass <math>I_i\neq R</math>.

Es ist <math>I_1\cdots I_r=I_1\cdot R\cdots R=I_1=I</math> und außerdem

<math>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}^nR/I_i</math>

== Weblinks ==
{{Wikibooks|Beweisarchiv: Algebra: Ringe: Chinesischer Restsatz|Beweis des Satzes im Beweisarchiv}}
* [http://www.arndt-bruenner.de/mathe/scripts/chinesischerRestsatz.htm Programm zur Berechnung simultaner Kongruenzen]
* [https://www.encyclopediaofmath.org/index.php/Chinese_remainder_theorem ''Chinese Remainder Theorem''] in der ''[[Encyclopaedia of Mathematics]]''
* {{MathWorld |id=ChineseRemainderTheorem |title=Chinese Remainder Theorem}}
* [[Christian Spannagel]]: [https://av.tib.eu/series/249 Chinesischer Restsatz]. Vorlesungsreihe, 2012.
* [http://planetmath.org/ChineseRemainderTheorem Chinese Remainder Theorem.] Planetmath.org (englisch).

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4470755-1|LCCN=sh/97/2778}}

[[Kategorie:Satz (Zahlentheorie)]]
[[Kategorie:Algebra]]

Chinesischer Restsatz - Versionsgeschichte

imported>Mathze: Die letzte Textänderung von 195.37.234.83 wurde verworfen und die Version 256361361 von Jule Glühwurm wiederhergestellt.