Der chinesische Restsatz

Motivation

Als Motivation gelte einmal folgendes Beispiel: Ich habe $x$ Bonbons. Wenn ich diese Bonbons an $4$ Personen verteile, bleiben $2$ Bonbons übrig. Wenn ich sie an $7$ Personen verteile, bleiben $3$ Bonbons übrig. Wie viele Bonbons habe ich?

Es gilt:

• $x\equiv 2$ mod $4$
• $x\equiv 3$ mod $7$

Wie gehe ich vor? Ich habe einen "Trick". :-) ... Ich suche zunächst die Inversen der Moduln zueinander, also

• $7x_1\equiv1$ mod $4$
• $4x_2\equiv1$ mod $7$

(Diese existieren, weil beide Moduln teilerfremd sind). Wir kommen (in diesem einfachen Fall mit ein bisschen überlegen) auf

• $x_1=3$
• $x_2=2$.

Und jetzt rechne ich... moooment... $2\cdot 7\cdot 3 + 3\cdot 4\cdot 2 = 42 + 24 = 66$. Ja, genau. $66$ Bonbons hab ich, ne? (oder 94... oder 122... oder 150... mmmh... oder 38... oder 10... :-)).

Verallgemeinerung auf zwei Moduln

Seien $m_1$ und $m_2$ teilerfremd. Zu lösen sei das Kongruenzsystem:

• $x\equiv a_1$ mod $m_1$
• $x\equiv a_2$ mod $m_2$

Man bestimmt Zahlen $x_1$ und $x_2$ folgendermaßen:

• $m_2\cdot x_1 \equiv 1$ mod $m_1$
• $m_1\cdot x_2 \equiv 1$ mod $m_2$

Dann ist eine Lösung $x = a_1\cdot x_1\cdot m_2 + a_2\cdot x_2\cdot m_1$, denn

• $x\equiv a_1\cdot x_1\cdot m_2 + a_2\cdot x_2\cdot m_1 \equiv a_1\cdot 1 \equiv a_1$ mod $m_1$
• $x\equiv a_1\cdot x_1\cdot m_2 + a_2\cdot x_2\cdot m_1 \equiv a_2\cdot 1 \equiv a_2$ mod $m_2$

Weitere Lösungen ergeben sich durch $x+z\cdot m_1\cdot m_2$ (für $z\in\mathbb{Z}$)

So, und jetzt richtig allgemein: Der chinesische Restsatz

Die Zahlen $m_1, ..., m_n$ seien paarweise teilerfremd. Dann besitzt das Kongruenzsystem

• $x\equiv a_1$ mod $m_1$
• ...
• $x\equiv a_n$ mod $m_n$

eine Lösung mod $m=m_1\cdot...\cdot m_n$ und alle Lösungen liegen in derselben Kongruenzklasse modulo $m$.

Beweis: