Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Chinesischer Restesatz aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Chinesischer Restsatz

Chinesischer Restsatz 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$ existiert, dann sind mit $M\; :=$ kgV$(m\_1,\; m\_2,\; m\_3,\; \backslash ldots,\; m\_n)$ die Zahlen $x\; +\; kM\; \backslash \; (k\; \backslash in\; \backslash mathbb\{Z\})$ genau alle Lösungen. Es kann aber auch sein, dass es gar keine Lösung gibt.

Teilerfremde Moduln

Die Originalform des Chinesischen Restsatzes stammt vom Mathematiker Sun_Zi (3. Jhd.) und wurde 1247 von Ch'in Chiu-Shao wiederveröffentlicht. Der Satz trifft eine Aussage über simultane Kongruenzen für den Fall, dass die Moduln teilerfremd sind. Sie lautet:

Seien $m\_1,\; \backslash ldots,\; m\_n$ paarweise teilerfremde ganze Zahlen, dann existiert für jedes Tupel ganzer Zahlen $a\_1,\; \backslash ldots,\; a\_n$ eine ganze Zahl $x$, die die folgende simultane Kongruenz erfüllt:
: $x\; \backslash equiv\; a\_i\; \backslash mod\; m\_i$ für $i\; =\; 1,\; \backslash ldots,\; n$
Alle Lösungen dieser Kongruenz sind kongruent modulo $M\; :=\; m\_1\; m\_2\; m\_3\; \backslash ldots\; m\_n$.

Das Produkt $M$ stimmt hier wegen der Teilerfremdheit mit dem kgV überein.

Finden einer Lösung

Eine Lösung $x$ kann man wie folgt ermitteln. 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 Zahlen $r\_i$ und $s\_i$ finden, so dass
: $r\_i\; \backslash cdot\; m\_i\; +\; s\_i\; \backslash cdot\; M\_i\; =\; 1$.

Setzen wir $e\_i\; :=\; s\_i\; \backslash cdot\; M\_i$, dann gilt
: $e\_i\; \backslash equiv\; 1\; \backslash mod\; m\_i$
: $e\_i\; \backslash equiv\; 0\; \backslash mod\; m\_j,\; \backslash \; j\; \backslash neq\; i$.

Die Zahl
: $x\; :=\; \backslash 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\; \backslash cdot\; 4\; \backslash cdot\; 5\; =\; 60,\; \backslash \; M\_1\; =\; M/3\; =\; 20,\; \backslash \; M\_2\; =\; M/4\; =\; 15,\; \backslash \; M\_3\; =\; M/5\; =\; 12$.
Mit Hilfe des erweiterten_euklidischen_Algorithmus berechnet man
: $(-13)\; \backslash cdot\; 3\; +\; 2\; \backslash cdot\; 20\; =\; 1$, also $e\_1\; =\; 40$
: $(-11)\; \backslash cdot\; 4\; +\; 3\; \backslash cdot\; 15\; =\; 1$, also $e\_2\; =\; 45$
: $5\; \backslash cdot\; 5\; +\; (-2)\; \backslash cdot\; 12\; =\; 1$, also $e\_3\; =\; -24$

Eine Lösung ist dann $x\; =\; 2\; \backslash cdot\; 40\; +\; 3\; \backslash cdot\; 45\; +\; 2\; \backslash cdot\; (-24)\; =\; 167$. Wegen $167\; \backslash equiv\; 47\; \backslash 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\; \backslash neq\; j$ gilt:
: $a\_i\; \backslash equiv\; a\_j\; \backslash mod$ ggT$(m\_i,\; m\_j)$.
Alle Lösungen sind dann kongruent modulo dem 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\; \backslash equiv\; 1\; \backslash mod\; \backslash 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.

Aussage für Hauptidealringe

Sei $R$ ein Hauptidealring, dann lautet der Chinesische Restsatz für $R$ so:

Sind $m\_1,\; \backslash ldots,\; m\_n$ paarweise teilerfremd und $m$ ihr Produkt, dann ist der Faktorring $R/mR$ isomorph zum Produktring $R/m\_1\; R\; \backslash times\; \backslash ldots\; \backslash times\; R/m\_n\; R$ durch den Isomorphismus
:$$
\begin{matrix}
f : & R/mR & \to & R/m_1R \times \ldots \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 $R$ (mit Einselement).

Sind $I\_1,\; \backslash ldots,\; I\_n$ (beidseitige) Ideale, so dass $I\_i\; +\; I\_j\; =\; R$ für $i\; \backslash neq\; j$ (man nennt die Ideale dann teilerfremd oder komaximal), und sei $I$ das Produkt der Ideale, dann ist $I$ gleich dem Durchschnitt der $I\_j$ und der Faktorring $R/I$ ist isomorph zum Produktring
$R/I\_1\; \backslash times\; \backslash ldots\; \backslash times\; R/I\_n$ durch den Isomorphismus
:$$
\begin{matrix}
f : & R/I & \to & R/I_1 \times \ldots \times R/I_n \\
& x + I & \mapsto & (x + I_1, \ldots, x + I_n)
\end{matrix}

zh-classical:????

beat

       VIDEO-NEWS UND ANGEBOTE