Nachlesen

Chinesischer Restsatz

Beim chinesischen Restsatz (auch chinesischer Restklassensatz genannt) handelt es sich um mehrere ähnliche Theoreme aus der abstrakten Algebra und der Zahlentheorie, mit denen simultane Kongruenzen berechnet werden können.

Die ursprüngliche Version des chinesischen Restsatzes, die sich mit der Lösung simultaner Kongruenzen für teilerfremde Moduln befasst, geht auf den chinesischen Mathematiker Sun Tzu zurück, der ihn vermutlich im 3. Jahrhundert in seinem Buch Sūn Zǐ Suànjīng (Sun Tzus Handbuch der Arithmetik) niederschrieb.

Inhalt

Definition
Beschreibung des Verfahrens
Beispiele
Beweise
Beweise (abstrakte Algebra)

Definition

Simultane Kongruenz ganzer Zahlen

Bei einer simultanen Kongruenz ganzer Zahlen handelt es sich um ein System von linearen Kongruenzen:

\begin{align*} x &\equiv a_1 \pmod{m_1} \\[0.5em] x &\equiv a_2 \pmod{m_2} \\[0.5em] &\ \ \vdots \\[0.5em] x &\equiv a_n \pmod{m_n}. \end{align*}

Für das System sollen – falls existent – alle ganzen Zahlen \(x\) bestimmt werden, die diese Kongruenzen gleichzeitig (also simultan) erfüllen. Falls eine solche Lösung \(x_0\) existiert, so handelt es sich bei den Zahlen

x_0 + kM \quad(\text{für } k \in \Z \text{ und } M = \kgV(m_1,\ldots,m_n))

ebenfalls um Lösungen des Systems. Bei \(M\) handelt es sich hierbei um das kleinste gemeinsame Vielfache der Moduln \(m_1,\ldots,m_n\). Bei den Werten \(x_0 + kM\) handelt es sich um die Elemente der Restklasse \({[x_0]}_M\). Häufig wird für den Wert \(x_0\) der Standardvertreter der entsprechenden Restklasse verwendet; für diesen gilt \(0 \leq x_0 \lt M\).

Chinesischer Restsatz für Kongruenzen mit teilerfremden Moduln

Zunächst wird die ursprüngliche Version des chinesischen Restsatzes betrachtet, die das Problem der simultanen Kongruenzen für teilerfremde Moduln umfasst.

Seien \(m_1,\ldots,m_n\) paarweise teilerfremde natürliche Zahlen und sei \(M = m_1 \cdot \ldots \cdot m_n\) das Produkt dieser Zahlen. Für ganze Zahlen \(a_1,\ldots,a_n\) existiert dann ein ganzzahliges \(x_0\) mit \(0 \leq x_0 \lt M\), das die folgende simultane Kongruenz erfüllt:

x \equiv a_i \pmod{m_i} \quad(\text{für } 1 \leq i \leq n).

Alle Lösungen \(x\) dieses Systems sind kongruent modulo \(M\). Aufgrund der Teilerfremdheit der Moduln \(m_1,\ldots,m_n\) handelt es sich beim Produkt \(M\) zudem um das kleinste gemeinsame Vielfache der Zahlen \(m_1,\ldots,m_n\).

Verallgemeinerung für Kongruenzen mit nicht teilerfremden Moduln

Seien \(m_1,\ldots,m_n\) natürliche Zahlen. Für ganze Zahlen \(a_1,\ldots,a_n\) existiert genau dann ein ganzzahliges \(x\), das die simultane Kongruenz

x \equiv a_i \pmod{m_i} \quad(\text{für } 1 \leq i \leq n)

erfüllt, falls für alle \(i \neq j\) stets

a_i \equiv a_j \pmod{\ggT(m_i, m_j)}

gilt. Mit \(\ggT(m_i, m_j)\) ist hierbei der größte gemeinsame Teiler von \(m_i\) und \(m_j\) bezeichnet. Alle Lösungen \(x\) dieser Kongruenz sind kongruent modulo \(M = \kgV(m_1, \ldots, m_n)\).

Formale Definition in der abstrakten Algebra

Seien \(m_1,\ldots,m_n\) paarweise teilerfremde natürliche Zahlen und \(a_1,\ldots,a_n\) ganze Zahlen. Nach dem chinesischen Restsatz besitzt die simultane Kongruenz

x \equiv a_i \pmod{m_i} \quad(\text{für } 1 \leq i \leq n)

dann stets ganzzahlige Lösungen \(x\), die alle kongruent modulo \(M = m_1 \cdot \ldots \cdot m_n\) sind. Gemäß der Definition von Restklassen folgt aus \(x \equiv a_i \pmod{m_i}\) stets \({[x]}_{m_i} = {[a_i]}_{m_i}\). Analog folgt aus der Kongruenz der Lösungen deren Zugehörigkeit zur Restklasse \({[x]}_M\). Jedem Tupel \(\bigl({[a_1]}_{m_1}, \ldots, {[a_n]}_{m_n} \bigr) = \bigl({[x]}_{m_1}, \ldots, {[x]}_{m_n}\bigr)\) kann also stets eine Restklasse \({[x]}_M\) zugeordnet werden – und umgekehrt.

In der abstrakten Algebra kann der chinesische Restsatz nun wie folgt formuliert werden: Für teilerfremde natürliche Zahlen \(m_1,\ldots,m_n\) sowie die Zahl \(M = m_1 \cdot \ldots \cdot m_n\) handelt es sich bei der Abbildung

\begin{array}{c} \Z_M \rightarrow \Z_{m_1} \times \ldots \times \Z_{m_n} \\[0.5em] {[x]}_M \mapsto \bigl( {[x]}_{m_1}, \ldots, {[x]}_{m_n} \bigr) \end{array}

des Restklassenrings \(\Z_M\) auf den Ring \(\Z_{m_1} \times \ldots \times \Z_{m_n}\) (das kartesische Produkt der Restklassenringe \(\Z_{m_1}, \ldots, \Z_{m_n}\)) um einen Ringisomorphismus, d. h. um eine strukturerhaltende, bijektive Abbildung zwischen den beiden Ringen.

Dies ermöglicht es, arithmetische Operationen in \(\Z_M\) nicht direkt in \(\Z_M\) durchzuführen; stattdessen werden die Operationen stellvertretend für alle \(\Z_{m_i}\) aus \(\Z_{m_1} \times \ldots \times \Z_{m_n}\) separat durchgeführt und das erhaltene Ergebnis anschließend mithilfe des Isomorphismus (über die garantiert existierende Umkehrabbildung) auf das eindeutige Ergebnis in \(\Z_M\) zurückgeführt. Insbesondere für große Werte von \(M\) und eine große Anzahl an Operationen ermöglicht dies – verglichen mit dem direkten Ausrechnen in \(\Z_M\) – eine oftmals deutlich schnellere Berechnung des Ergebnisses.

Beschreibung des Verfahrens

Chinesischer Restsatz für zwei Kongruenzen mit teilerfremden Moduln

Gegeben sei das folgende System aus zwei Kongruenzen mit teilerfremden natürlichen Moduln \(m_1,m_2\) und beliebigen ganzen Zahlen \(a_1,a_2\).

\begin{align*} x &\equiv a_1 \pmod{m_1} \\[0.5em] x &\equiv a_2 \pmod{m_2} \end{align*}

Aufgrund der Teilerfremdheit der Werte \(m_1\) und \(m_2\) können ganze Zahlen \(s_1\) und \(s_2\) gefunden werden, sodass

s_1 \cdot m_1 + s_2 \cdot m_2 = 1

gilt; diese können beispielsweise mit dem erweiterten euklidischen Algorithmus berechnet werden.

Mithilfe der Werte \(s_1\) und \(s_2\) kann die gesuchte Lösung der simultanen Kongruenz nun direkt berechnet werden; es gilt:

x = a_1 \cdot s_2 \cdot m_2 + a_2 \cdot s_1 \cdot m_1.

Chinesischer Restsatz für beliebig viele Kongruenzen mit teilerfremden Moduln

Gegeben sei das folgende System aus \(n\) Kongruenzen mit paarweise teilerfremden natürlichen Moduln \(m_1,\ldots,m_n\) und beliebigen ganzen Zahlen \(a_1,\ldots,a_n\).

\begin{align*} x &\equiv a_1 \pmod{m_1} \\[0.5em] &\ \ \vdots \\[0.5em] x &\equiv a_n \pmod{m_n} \end{align*}

Zunächst werden das Produkt \(M = m_1 \cdot \ldots \cdot m_n\) sowie die Werte \(M_i = \frac{M}{m_i}\) berechnet. Aufgrund der Teilerfremdheit der Werte \(m_i\) und \(M_i\) können nun ganze Zahlen \(r_i\) und \(s_i\) gefunden werden, sodass

r_i \cdot m_i + s_i \cdot M_i = 1 \quad(\text{für } 1 \leq i \leq n)

gilt; diese können beispielsweise mit dem erweiterten euklidischen Algorithmus berechnet werden.

Mithilfe der Werte \(s_i\) und \(M_i\) kann die gesuchte Lösung der simultanen Kongruenz nun direkt berechnet werden; es gilt:

x = \sum\limits_{i=1}^{n}{a_i \cdot s_i \cdot M_i}

Details zur Herleitung und zum Beweis der Formel können im Abschnitt Beweise nachgelesen werden.

Chinesischer Restsatz für beliebig viele Kongruenzen mit nicht teilerfremden Moduln

Gegeben sei das folgende System aus \(n\) Kongruenzen mit natürlichen Moduln \(m_1,\ldots,m_n\) und beliebigen ganzen Zahlen \(a_1,\ldots,a_n\).

\begin{align*} x &\equiv a_1 \pmod{m_1} \\[0.5em] &\ \ \vdots \\[0.5em] x &\equiv a_n \pmod{m_n} \end{align*}

Wichtig: Die Teilerfremdheit der Moduln \(m_1,\ldots,m_n\) ist nicht garantiert. Eine Lösung existiert nur für den Fall, dass für alle \(i \neq j\) stets \(a_i \equiv a_j \pmod{\ggT(m_i, m_j)}\) gilt. Der nachfolgende Abschnitt bezieht sich ausschließlich auf den Fall, dass die vorausgehende Bedingung erfüllt ist!

Die Lösung der simultanen Kongruenz – falls existent – kann beispielsweise durch sukzessive Substitution gelöst werden, indem die Kongruenzen schrittweise zusammengefasst bzw. ersetzt werden. Beispielsweise können Kongruenzen der Form

\begin{align*} x &\equiv a \pmod{m_1} \\[0.5em] &\ \ \vdots \\[0.5em] x &\equiv a \pmod{m_n} \end{align*}

direkt zur folgenden Bedingung zusammengefasst werden:

x \equiv a \pmod{\kgV(m_1,\ldots,m_n)}.

Allgemein können Kongruenzen mit nicht teilerfremden Moduln mithilfe der Primfaktorzerlegungen der Moduln zusammengefasst bzw. ersetzt werden. Hierzu seien \(m_1\) und \(m_2\) exemplarisch zwei nicht teilerfremde Moduln mit den Primfaktorzerlegungen \(m_1 = p_1^{\alpha_1} \cdot p_2^{\alpha_2}\) und \(m_2 = p_2^{\beta_2} \cdot p_3^{\beta_3}\), die aus den drei Primzahlen \(p_1\), \(p_2\) und \(p_3\) bestehen, die jeweils in den Vielfachheiten \(\alpha_1\), \(\alpha_2\), \(\beta_2\) und \(\beta_3\) vorkommen. Die originalen Kongruenzen können nun durch die nachfolgenden Kongruenzen ersetzt werden, bei deren Moduln es sich um die in den Primfaktorzerlegungen vorkommenden Primzahlpotenzen handelt:

\begin{align*} x &\equiv a_1 \pmod{p_1^{\alpha_1}} \\[0.5em] x &\overset{\star}{\equiv} a_1 \pmod{p_2^{\alpha_2}} \\[0.5em] x &\overset{\star}{\equiv} a_2 \pmod{p_2^{\beta_2}} \\[0.5em] x &\equiv a_2 \pmod{p_3^{\beta_3}}. \end{align*}

Die Moduln der beiden mit \(\star\) markierten Kongruenzen sind Potenzen derselben Primzahl \(p_2\) und somit nicht teilerfremd. Gesetzt dem Fall, dass \(a_1 \equiv a_2 \pmod{\ggT(p_2^{\alpha_2}, p_2^{\beta_2})}\) gilt, kann die Kongruenz mit der kleineren Primzahlpotenz gestrichen werden. Dies kann anschließend solange wiederholt werden, bis alle verbleibenden Moduln teilerfremd sind. (Hinweis: Dies kann auch für alle Kongruenzen parallel durchgeführt werden.) Anschließend kann das reguläre Lösungsverfahren für teilerfremde Moduln verwendet werden.

Beispiele

Beispiel 1: Zwei Kongruenzen mit teilerfremden Moduln

Es soll die Lösung der folgenden simultanen Kongruenz mithilfe des chinesischen Restsatzes bestimmt werden:

\begin{align*} x &\equiv 3 \pmod{5} \\[0.5em] x &\equiv 4 \pmod{9}. \end{align*}

Zunächst müssen ganze Zahlen \(s\) und \(t\) bestimmt werden, sodass

s \cdot 5 + t \cdot 9 = 1

gilt. Die Lösung \(s=2\) und \(t=-1\) kann hierbei beispielsweise durch Ausprobieren schnell gefunden werden; alternativ natürlich auch mit Verfahren wie dem erweiterten euklidischen Algorithmus.

Für die Lösung der simultanen Kongruenz ergibt sich somit:

\begin{align*} x &= a_1 \cdot t \cdot m_2 + a_2 \cdot s \cdot m_1 \\[0.5em] &= 3 \cdot (-1) \cdot 9 + 4 \cdot 2 \cdot 5 \\[0.5em] &= 13. \end{align*}

Die Gültigkeit der gefundenen Lösung kann leicht überprüft werden: Es gilt \(13 \equiv 3 \pmod{5}\) sowie \(13 \equiv 4 \pmod{9}\). Alle Lösungen sind somit kongruent zu \(13\) modulo \(45\).

Beispiel 2: Drei Kongruenzen mit teilerfremden Moduln

Es soll die Lösung der folgenden simultanen Kongruenz mithilfe des chinesischen Restsatzes bestimmt werden:

\begin{align*} x &\equiv 2 \pmod{3} \\[0.5em] x &\equiv 3 \pmod{5} \\[0.5em] x &\equiv 4 \pmod{7}. \end{align*}

Zunächst werden die Werte \(M\), \(M_1\), \(M_2\) und \(M_3\) bestimmt. Es gilt:

\begin{align*} M &= 3 \cdot 5 \cdot 7 = 105 \\[0.5em] M_1 &= \frac{M}{3} = \frac{105}{3} = 35 \\[0.5em] M_2 &= \frac{M}{5} = \frac{105}{5} = 21 \\[0.5em] M_3 &= \frac{M}{7} = \frac{105}{7} = 15. \end{align*}

Anschließend müssen ganze Zahlen \(r_1\), \(r_2\), \(r_3\), \(s_1\), \(s_2\) und \(s_3\) bestimmt werden, sodass die folgenden Gleichungen gelten.

\begin{align*} \begin{alignedat}{2} r_1 \cdot 3 + s_1 \cdot 35 &= 1 & \quad\Rightarrow\quad & r_1 = 12 \text{ und } s_1 = -1 \\[0.5em] r_2 \cdot 5 + s_2 \cdot 21 &= 1 & \quad\Rightarrow\quad & r_2 = -4 \text{ und } s_2 = 1 \\[0.5em] r_3 \cdot 7 + s_3 \cdot 15 &= 1 & \quad\Rightarrow\quad & r_3 = -2 \text{ und } s_3 = 1 \\[0.5em] \end{alignedat} \end{align*}

Für die Lösung der simultanen Kongruenz ergibt sich somit:

\begin{align*} x &= a_1 \cdot s_1 \cdot M_1 + a_2 \cdot s_2 \cdot M_2 + a_3 \cdot s_3 \cdot M_3 \\[0.5em] &= 2 \cdot (-1) \cdot 35 + 3 \cdot 1 \cdot 21 + 4 \cdot 1 \cdot 15 \\[0.5em] &= 53. \end{align*}

Die Gültigkeit der gefundenen Lösung kann leicht überprüft werden: Es gilt \(53 \equiv 2 \pmod{3}\), \(53 \equiv 3 \pmod{5}\) sowie \(53 \equiv 4 \pmod{7}\). Alle Lösungen sind somit kongruent zu \(53\) modulo \(105\).

Beispiel 3: Kongruenzen mit nicht teilerfremden Moduln

Es soll die Lösung der folgenden simultanen Kongruenz mithilfe des chinesischen Restsatzes bestimmt werden:

\begin{align*} x &\equiv 1 \pmod{2} \\[0.5em] x &\equiv 1 \pmod{3} \\[0.5em] x &\equiv 1 \pmod{4} \\[0.5em] x &\equiv 1 \pmod{5} \\[0.5em] x &\equiv 1 \pmod{6} \\[0.5em] x &\equiv 0 \pmod{7}. \end{align*}

Da beispielsweise die Moduln \(2\) und \(4\) nicht teilerfremd sind, kann nicht direkt das Lösungsverfahren für teilerfremde Moduln verwendet werden. Die ersten fünf Kongruenzen können jedoch leicht zusammengefasst werden:

x \equiv 1 \pmod{\underbrace{\kgV(2,3,4,5,6)}_{=\ 60}}.

Somit verbleiben die folgenden beiden Kongruenzen:

\begin{align*} x &\equiv 1 \pmod{60} \\[0.5em] x &\equiv 0 \pmod{7}. \end{align*}

Da die Moduln \(60\) und \(7\) teilerfremd sind, kann diese Aufgabe problemlos mit dem Lösungsverfahren für Kongruenzen mit teilerfremden Moduln gelöst werden. Dieses liefert, dass alle Lösungen kongruent zu \(301\) modulo \(420\) sind.

Beispiel 4: Kongruenzen mit nicht teilerfremden Moduln

Es soll die Lösung der folgenden simultanen Kongruenz mithilfe des chinesischen Restsatzes bestimmt werden:

\begin{align*} \begin{alignedat}{2} x &\equiv 7 && \pmod{12} \\[0.5em] x &\equiv 3 && \pmod{40} \\[0.5em] x &\equiv 43 && \pmod{90}. \end{alignedat} \end{align*}

Da die Moduln \(12\), \(40\) und \(90\) nicht teilerfremd sind, kann das Lösungsverfahren für teilerfremde Moduln nicht direkt verwendet werden.

Zunächst werden die Primfaktorzerlegungen der Moduln bestimmt; es gilt:

\begin{align*} 12 &= 2^2 \cdot 3 \\[0.5em] 40 &= 2^3 \cdot 5 \\[0.5em] 90 &= 2 \cdot 3^2 \cdot 5. \end{align*}

Damit können die originalen Kongruenzen wie folgt ersetzt werden:

\begin{align*} \begin{alignedat}{2} x &\overset{(1)}{\equiv} 7 \equiv 1 && \pmod{2^2} \\[0.5em] x &\overset{(2)}{\equiv} 7 \equiv 1 && \pmod{3} \\[0.5em] x &\overset{(3)}{\equiv} 3 && \pmod{2^3} \\[0.5em] x &\overset{(4)}{\equiv} 3 && \pmod{5} \\[0.5em] x &\overset{(5)}{\equiv} 43 \equiv 1 && \pmod{2} \\[0.5em] x &\overset{(6)}{\equiv} 43 \equiv 7 && \pmod{3^2} \\[0.5em] x &\overset{(7)}{\equiv} 43 \equiv 3 && \pmod{5}. \end{alignedat} \end{align*}

Da die Kongruenzen (1), (3) und (5) sich nicht gegenseitig widersprechen, können diese durch die Kongruenz \(x \equiv 3 \pmod{8}\) zusammengefasst werden: Jeder Wert, der bei Division durch \(8\) den Rest \(3\) lässt, lässt auch bei Division durch \(4\) den Rest \(3\) und bei Division durch \(2\) den Rest \(1\). Analog können die Kongruenzen (2) und (6) zu \(x \equiv 7 \pmod{9}\) sowie die Kongruenzen (4) und (7) zu \(x \equiv 3 \pmod{5}\) zusammengefasst werden. Somit verbleiben die folgenden Kongruenzen mit nun teilerfremden Moduln:

\begin{align*} x &\equiv 3 \pmod{5} \\[0.5em] x &\equiv 3 \pmod{8} \\[0.5em] x &\equiv 7 \pmod{9}. \end{align*}

Lösen mit dem Verfahren für Kongruenzen mit teilerfremden Moduln liefert, dass alle Lösungen kongruent zu \(-1397\) bzw. \(43\) modulo \(360\) sind. Einsetzen der gefundenen Lösung in die ursprünglichen Kongruenzen bestätigt die Gültigkeit der Lösung.

Beweise

Beweis der Eindeutigkeit der Lösung

Gegeben sei das folgende System aus \(n\) Kongruenzen mit paarweise teilerfremden natürlichen Moduln \(m_1,\ldots,m_n\) und beliebigen ganzen Zahlen \(a_1,\ldots,a_n\); mit \(M = m_1 \cdot \ldots \cdot m_n\) sei das Produkt der Moduln bezeichnet.

\begin{align*} x &\equiv a_1 \pmod{m_1} \\[0.5em] &\ \ \vdots \\[0.5em] x &\equiv a_n \pmod{m_n}. \end{align*}

Angenommen, bei \(x\) und \(y\) handelt es sich um Lösungen aller Kongruenzen. Es gilt demnach \(x \equiv a_i \pmod{m_i}\) sowie \(y \equiv a_i \pmod{m_i}\), woraus aufgrund der Transitivität der Kongruenzrelation auch die Kongruenz \(x \equiv y \pmod{m_i}\) folgt, und somit die Teilbarkeit \(m_i \mid (x-y)\). Da die Moduln \(m_i\) paarweise teilerfremd sind, folgt hieraus insbesondere die Teilbarkeit \(M \mid (x-y)\), und somit die Kongruenz \(x \equiv y \pmod{M}\). Bei der Differenz \(x-y\) handelt es sich also um ein Vielfaches von \(M\). Unter Berücksichtigung der Forderungen \(0 \leq x \lt M\) bzw. \(0 \leq y \lt M\) folgt hieraus \(x=y\) und somit die Eindeutigkeit der Lösung, da es sich bei \(x-y=0\) um das einzige, unter diesen Voraussetzungen in Frage kommende Vielfache von \(M\) handelt.

Beweis der Existenz der Lösung (vollständige Induktion)

Die Existenz einer Lösung der simultanen Kongruenz mit \(n\) Kongruenzen kann mittels vollständiger Induktion gezeigt werden, indem zunächst eine Lösung für eine spezielle Anzahl \(n\) an Kongruenzen (z. B. für \(n=2\)) direkt berechnet und anschließend gezeigt wird, dass unter der Annahme, die simultane Kongruenz sei für \(n\) Kongruenzen lösbar, dann auch eine Lösung für die simultane Kongruenz mit \(n+1\) Kongruenzen berechnet werden kann.

(I) Induktionsanfang
Gegeben sei das folgende System aus \(n=2\) Kongruenzen mit teilerfremden natürlichen Moduln \(m_1\) und \(m_2\):

\begin{align*} x &\equiv a_1 \pmod{m_1} \\[0.5em] x &\equiv a_2 \pmod{m_2}. \end{align*}

Nach dem Lemma von Bézout existieren ganze Zahlen \(s_1\) und \(s_2\) mit

s_1 \cdot m_1 + s_2 \cdot m_2 = 1,

die beispielsweise mit dem erweiterten euklidischen Algorithmus berechnet werden können. Mithilfe der Werte \(s_1\) und \(s_2\) kann nun eine Lösung \(x\) der simultanen Kongruenz wie folgt berechnet werden:

x = a_1 \cdot s_2 \cdot m_2 + a_2 \cdot s_1 \cdot m_1.

Um zu überprüfen, dass es sich bei \(x\) tatsächlich um die gesuchte Lösung handelt, können die beiden Kongruenzen durch Nachrechnen gezeigt werden. Für den Beweis der Kongruenz \(x \equiv a_1 \pmod{m_1}\) ergibt sich:

\begin{align*} x &\overset{(1)}{=} a_1 \cdot s_2 \cdot m_2 + a_2 \cdot s_1 \cdot m_1 \\[0.5em] &\overset{(2)}{=} a_1 \cdot \bigl( 1 - s_1 \cdot m_1 \bigr) + a_2 \cdot s_1 \cdot m_1 \\[0.5em] &\overset{(3)}{=} a_1 - a_1 \cdot s_1 \cdot m_1 + a_2 \cdot s_1 \cdot m_1 \\[0.5em] &\overset{(4)}{=} a_1 + \underbrace{\bigl(a_2 - a_1 \bigr) \cdot s_1 \cdot m_1}_{\equiv\ 0 \pmod{m_1}} \\[0.5em] &\overset{(5)}{\equiv} a_1 \pmod{m_1}. \end{align*}

Erklärungen zu den Schritten
(2)	Ersetzen von \(s_2 \cdot m_2\) mithilfe der entsprechend umgestellten Gleichung \(s_1 \cdot m_1 + s_2 \cdot m_2 = 1\)
(3)	Ausmultiplizieren mithilfe des Distributivgesetzes
(4)	Ausklammern von \(s_1 \cdot m_1\) mithilfe des Distributivgesetzes
(5)	Anwenden der Kongruenz für modulare Addition

Analog lässt sich die Kongruenz \(x \equiv a_2 \pmod{m_2}\) zeigen:

\begin{align*} x &= a_1 \cdot s_2 \cdot m_2 + a_2 \cdot s_1 \cdot m_1 \\[0.5em] &= a_1 \cdot s_2 \cdot m_2 + a_2 \cdot \bigl( 1 - s_2 \cdot m_2 \bigr) \\[0.5em] &= a_1 \cdot s_2 \cdot m_2 + a_2 - a_2 \cdot s_2 \cdot m_2 \\[0.5em] &= a_2 + \underbrace{\bigl(a_1 - a_2 \bigr) \cdot s_2 \cdot m_2}_{\equiv\ 0 \pmod{m_2}} \\[0.5em] &\equiv a_2 \pmod{m_2}. \end{align*}

(II) Induktionsschritt
Induktionsannahme: Die simultane Kongruenz gelte für ein festes \(n \in \N\) mit \(n \geq 2\).

Gegeben sei das folgende System aus \(n+1\) Kongruenzen mit teilerfremden natürlichen Moduln \(m_1, \ldots, m_{n+1}\):

\begin{align*} \begin{alignedat}{2} x &\equiv a_1 && \pmod{m_1} \\[0.5em] &\ \ \vdots && \\[0.5em] x &\equiv a_n&& \pmod{m_n} \\[0.5em] x &\equiv a_{n+1} && \pmod{m_{n+1}}. \end{alignedat} \end{align*}

Gemäß Induktionsannahme existiert für die Kongruenzen \(x \equiv a_i \pmod{m_i}\) mit \(1 \leq i \leq n\) eine Lösung, die als \(a_{1 \ldots n}\) bezeichnet wird. Hiermit lässt sich das System mit \(n+1\) Kongruenzen in die folgende Form überführen:

\begin{align*} \begin{alignedat}{2} x &\equiv a_{1 \ldots n} && \pmod{m_1 \cdot \ldots \cdot m_n} \\[0.5em] x &\equiv a_{n+1} && \pmod{m_{n+1}}. \end{alignedat} \end{align*}

Die Moduln \(m_1 \cdot \ldots \cdot m_n\) und \(m_{n+1}\) sind aufgrund der paarweisen Teilerfremdheit der Zahlen \(m_1,\ldots,m_{n+1}\) ebenfalls teilerfremd, sodass erneut der bereits im Induktionsanfang beschriebene (und lösbare!) Fall mit genau zwei Kongruenzen vorliegt; dieser liefert die gesuchte Lösung \(x\) für die gegebenen \(n+1\) Kongruenzen.

Insgesamt folgt, dass die simultane Kongruenz für \(n+1\) Kongruenzen gelöst werden kann, falls sie für \(n\) Kongruenzen gelöst werden kann. Gemeinsam mit dem Induktionsanfang folgt somit die Lösbarkeit für alle \(n \in \N\) mit \(n \geq 2\).

Beweis der Existenz der Lösung (direktes Nachrechnen)

Die Existenz einer Lösung der simultanen Kongruenz mit \(n\) Kongruenzen kann auch durch direktes Nachrechnen ohne vollständige Induktion gezeigt werden.

Gegeben sei das folgende System aus \(n\) Kongruenzen mit paarweise teilerfremden natürlichen Moduln \(m_1,\ldots,m_n\) und beliebigen ganzen Zahlen \(a_1,\ldots,a_n\).

\begin{align*} x &\equiv a_1 \pmod{m_1} \\[0.5em] &\ \ \vdots \\[0.5em] x &\equiv a_n \pmod{m_n}. \end{align*}

Mit \(M = m_1 \cdot \ldots \cdot m_n\) sei das Produkt aller Moduln bezeichnet. Hiermit werden nun zunächst Werte \(M_i = \frac{M}{m_i}\) (für \(1 \leq i \leq n\)) definiert; es handelt sich bei \(M_i\) also um das Produkt aller Moduln mit Ausnahme von \(m_i\). Aufgrund der Teilerfremdheit der Moduln folgt somit unmittelbar die Teilerfremdheit von \(m_1\) und \(M_1\). Nach dem Lemma von Bézout existieren somit ganze Zahlen \(r_i\) und \(s_i\) mit

r_i \cdot m_i + s_i \cdot M_i = 1 \quad(\text{für } 1 \leq i \leq n),

die beispielsweise mit dem erweiterten euklidischen Algorithmus berechnet werden können. Mithilfe der Werte \(s_i\) und \(r_i\) kann nun eine Lösung \(x\) der simultanen Kongruenz wie folgt berechnet werden:

x = \sum\limits_{i=1}^{n}{a_i \cdot s_i \cdot M_i}

Um zu überprüfen, dass es sich bei \(x\) tatsächlich um die gesuchte Lösung handelt, können die Kongruenzen durch Nachrechnen gezeigt werden. Für den Beweis der Kongruenz \(x \equiv a_k \pmod{m_k}\) ergibt sich:

\begin{align*} \begin{alignedat}{2} x &\overset{(1)}{=} \sum\limits_{i=1}^{n}{a_i \cdot s_i \cdot M_i} && \\[0.5em] &\overset{(2)}{=} a_k \cdot s_k \cdot M_k + \underbrace{\sum\limits_{i=1}^{k-1}{a_i \cdot s_i \cdot M_i}}_{\equiv\ 0 \pmod{m_k}} + \underbrace{\sum\limits_{i=k+1}^{n}{a_i \cdot s_i \cdot M_i}}_{\equiv\ 0 \pmod{m_k}} && \\[0.5em] &\overset{(3)}{\equiv} a_k \cdot s_k \cdot M_k && \llap{\pmod{m_k}} \\[0.5em] &\overset{(4)}{\equiv} a_k \cdot \bigl(1 - r_k \cdot m_k \bigr) && \llap{\pmod{m_k}} \\[0.5em] &\overset{(5)}{\equiv} a_k - \underbrace{a_k \cdot r_k \cdot m_k}_{\equiv\ 0 \pmod{m_k}} && \llap{\pmod{m_k}} \\[0.5em] &\overset{(6)}{\equiv} a_k && \llap{\pmod{m_k}}. \end{alignedat} \end{align*}

Erklärungen zu den Schritten
(2)	Herausziehen des \(k\)-ten Summanden aus der Summe Die Kongruenzen gelten wegen der Teilbarkeit \(m_k \mid M_i\) für alle \(i \neq k\)
(3)	Anwenden der Kongruenz für modulare Addition
(4)	Ersetzen von \(s_k \cdot M_k\) mithilfe der entsprechend umgestellten Gleichung \(r_k \cdot m_k + s_k \cdot M_k = 1\)
(5)	Ausmultiplizieren mithilfe des Distributivgesetzes
(6)	Anwenden der Kongruenz für modulare Addition

Beweise (abstrakte Algebra)

Beweis der Wohldefiniertheit

Seien \(m_1,\ldots,m_n\) paarweise teilerfremde natürliche Zahlen und sei \(M = m_1 \cdot \ldots \cdot m_n\) das Produkt dieser Zahlen. Zum Beweis der Wohldefiniertheit der Abbildung

\begin{array}{c} \Z_M \rightarrow \Z_{m_1} \times \ldots \times \Z_{m_n} \\[0.5em] {[x]}_M \mapsto \bigl( {[x]}_{m_1}, \ldots, {[x]}_{m_n} \bigr) \end{array}

muss gezeigt werden, dass für alle ganzen Zahlen \(x,y\) mit \({[x]}_M = {[y]}_M\) stets auch die Bilder \(\bigl( {[x]}_{m_1}, \ldots, {[x]}_{m_n} \bigr)\) und \( \bigl( {[y]}_{m_1}, \ldots, {[y]}_{m_n} \bigr)\) übereinstimmen, dass also \({[x]}_{m_i} = {[y]}_{m_i}\) gilt (für \(1 \leq i \leq n\)). Dies kann wie folgt gezeigt werden:

\begin{array}{l} {[x]}_M = {[y]}_M \\[0.5em] \quad\overset{(1)}{\Rightarrow} x \equiv y \pmod{M} \\[0.5em] \quad\overset{(2)}{\Rightarrow} M \mid (x-y) \\[0.5em] \quad\overset{(3)}{\Rightarrow} m_1 \mid (x-y) \ \wedge \ldots \wedge m_n \mid (x-y) \\[0.5em] \quad\overset{(4)}{\Rightarrow} x \equiv y \pmod{m_1} \ \wedge \ \ldots \ \wedge \ x \equiv y \pmod{m_n} \\[0.5em] \quad\overset{(5)}{\Rightarrow} {[x]}_{m_1} = {[y]}_{m_1} \ \wedge \ \ldots \ \wedge \ {[x]}_{m_n} = {[y]}_{m_n} \end{array}

Erklärungen zu den Schritten
(1)	Definition von Restklassen
(2)	Definition der Kongruenz
(3)	Transitivität der Teilbarkeitsrelation Es gilt \(m_i \mid M\) für alle \(i\) mit \(1 \leq i \leq n\)
(4)	Definition der Kongruenz
(5)	Definition von Restklassen

Beweis der Injektivität

Seien \(m_1,\ldots,m_n\) paarweise teilerfremde natürliche Zahlen und sei \(M = m_1 \cdot \ldots \cdot m_n\) das Produkt dieser Zahlen. Zum Beweis der Injektivität der Abbildung

\begin{array}{c} h: \Z_M \rightarrow \Z_{m_1} \times \ldots \times \Z_{m_n} \\[0.5em] {[x]}_M \mapsto \bigl( {[x]}_{m_1}, \ldots, {[x]}_{m_n} \bigr) \end{array}

muss gezeigt werden, dass für alle ganzen Zahlen \(x,y\) aus \(h({[x]}_M) = h({[y]}_M)\) stets \({[x]}_M = {[y]}_M\) folgt. Dies kann wie folgt gezeigt werden:

\begin{array}{l} h({[x]}_M) = h({[y]}_M) \\[0.5em] \quad\overset{(1)}{\Rightarrow} \bigl( {[x]}_{m_1}, \ldots, {[x]}_{m_n} \bigr) = \bigl( {[y]}_{m_1}, \ldots, {[y]}_{m_n} \bigr) \\[0.5em] \quad\overset{(2)}{\Rightarrow} {[x]}_{m_1} = {[y]}_{m_1} \ \wedge \ \ldots \ \wedge \ {[x]}_{m_n} = {[y]}_{m_n} \\[0.5em] \quad\overset{(3)}{\Rightarrow} x \equiv y \pmod{m_1} \ \wedge \ \ldots \ \wedge \ x \equiv y \pmod{m_n} \\[0.5em] \quad\overset{(4)}{\Rightarrow} m_1 \mid (x-y) \ \wedge \ldots \wedge m_n \mid (x-y) \\[0.5em] \quad\overset{(5)}{\Rightarrow} M \mid (x-y) \\[0.5em] \quad\overset{(6)}{\Rightarrow} x \equiv y \pmod{M} \\[0.5em] \quad\overset{(7)}{\Rightarrow} {[x]}_M = {[y]}_M \end{array}

Erklärungen zu den Schritten
(1)	Verwenden der Abbildungsvorschrift
(2)	Zwei Tupel sind genau dann gleich, wenn sie komponentenweise übereinstimmen
(3)	Definition von Restklassen
(4)	Definition der Kongruenz
(5)	Die Teilbarkeit durch \(M\) folgt aus der Tatsache, dass es sich bei \(M = m_1 \cdot \ldots \cdot m_n\) um das kleinste gemeinsame Vielfache der teilerfremden Zahlen \(m_1,\ldots,m_n\) handelt.
(6)	Definition der Kongruenz
(7)	Definition von Restklassen

Beweis der Surjektivität

Seien \(m_1,\ldots,m_n\) paarweise teilerfremde natürliche Zahlen und sei \(M = m_1 \cdot \ldots \cdot m_n\) das Produkt dieser Zahlen. Die Surjektivität der Abbildung

\begin{array}{c} \Z_M \rightarrow \Z_{m_1} \times \ldots \times \Z_{m_n} \\[0.5em] {[x]}_M \mapsto \bigl( {[x]}_{m_1}, \ldots, {[x]}_{m_n} \bigr) \end{array}

ergibt sich wie folgt: Die Menge \(\Z_M\) und das kartesische Produkt \(\Z_{m_1} \times \ldots \times \Z_{m_n}\) haben beide dieselbe Mächtigkeit; es gilt \(|\Z_M| = |\Z_{m_1} \times \ldots \times \Z_{m_n}| = m_1 \cdot \ldots \cdot m_n\). Die Surjektivität der Abbildung folgt direkt aus der Eigenschaft, dass eine injektive Abbildung zwischen gleichmächtigen Mengen stets surjektiv (und somit bijektiv) ist. Die Injektivität der Abbildung wurde im vorausgehenden Abschnitt bewiesen.

Aus der Surjektivität folgt die Existenz einer Lösung. Aus der Injektivität folgt darüber hinaus die Eindeutigkeit der Lösung.