Chinesischer Restsatz

Studium

x \equiv a_i \!\!\pmod{m_i}\ (i = 1, \ldots, k) \;\Leftrightarrow\; x \equiv \sum_{i=1}^{k} a_i \, M_i \, y_i \pmod M

Voraussetzung: $m_1, \ldots, m_k \geq 2$ $paarweise$ $teilerfremd$ $,$ $M = m_1 \cdots m_k,$ $M_i = \tfrac{M}{m_i},$ $M_i \, y_i \equiv 1 \!\!\pmod{m_i}$

$x$: gesuchte ganze Zahl
$a_i$: vorgegebener Rest modulo m_i
$m_i$: Moduln, paarweise teilerfremd
$M$: Produkt aller Moduln
$M_i$: Produkt aller Moduln außer m_i
$y_i$: Inverses von M_i modulo m_i

Simultane Kongruenzen mit paarweise teilerfremden Moduln haben genau eine Lösung modulo dem Produkt der Moduln.

Erklärung

Der Chinesische Restsatz behandelt Systeme von Kongruenzen

x \equiv a_1 \pmod{m_1}, \quad \ldots, \quad x \equiv a_k \pmod{m_k}.

Sind die Moduln paarweise teilerfremd, dann hat das System immer eine Lösung, und diese ist modulo $M = m_1 \cdots m_k$ eindeutig. Alle Lösungen sind $x + j \cdot M$ mit $j \in \mathbb{Z}$ .

Konstruktion der Lösung:

$M$ und $M_i = M / m_i$ berechnen.
Zu jedem $M_i$ das Inverse $y_i$ modulo $m_i$ bestimmen, etwa mit dem erweiterten Euklidischen Algorithmus. Es existiert, weil $M_i$ zu $m_i$ teilerfremd ist.
$x = \sum a_i M_i y_i$ bilden und modulo $M$ reduzieren.

Warum das stimmt: Modulo $m_i$ sind alle Summanden mit $j \neq i$ gleich $0$ , weil $M_j$ den Faktor $m_i$ enthält. Der $i$ -te Summand ist $a_i \cdot M_i y_i \equiv a_i \cdot 1$ .

Strukturell besagt der Satz, dass $\mathbb{Z}/M\mathbb{Z}$ und $\mathbb{Z}/m_1\mathbb{Z} \times \cdots \times \mathbb{Z}/m_k\mathbb{Z}$ isomorph sind. Daraus folgt auch die Multiplikativität der φ-Funktion.

Beispiele

Gesucht ist $x$ mit $x \equiv 1 \pmod 4$ , $x \equiv 2 \pmod 3$ , $x \equiv 3 \pmod 5$ .

$M = 4 \cdot 3 \cdot 5 = 60$ , $M_1 = 15$ , $M_2 = 20$ , $M_3 = 12$ .
$15 \equiv 3 \pmod 4$ , Inverses $y_1 = 3$ , da $9 \equiv 1$ .
$20 \equiv 2 \pmod 3$ , Inverses $y_2 = 2$ , da $4 \equiv 1$ .
$12 \equiv 2 \pmod 5$ , Inverses $y_3 = 3$ , da $6 \equiv 1$ .

x = 1 \cdot 15 \cdot 3 + 2 \cdot 20 \cdot 2 + 3 \cdot 12 \cdot 3 = 45 + 80 + 108 = 233 \equiv 53 \pmod{60}

Probe: $53 = 13 \cdot 4 + 1 = 17 \cdot 3 + 2 = 10 \cdot 5 + 3$ . Alle Lösungen sind $53 + 60j$ .

Typische Fehler

Nicht teilerfremde Moduln. $x \equiv 1 \pmod 4$ und $x \equiv 2 \pmod 6$ hat keine Lösung: Die erste Bedingung verlangt ein ungerades $x$ , die zweite ein gerades. Wegen $\operatorname{ggT}(4, 6) = 2$ greift der Satz nicht.
Das Inverse vergessen. $\sum a_i M_i$ allein ist im Allgemeinen keine Lösung; erst der Faktor $y_i$ macht $M_i y_i \equiv 1 \pmod{m_i}$ .
Nicht modulo $M$ reduzieren. $233$ ist auch eine Lösung, die kleinste nichtnegative ist aber $53$ .

Chinesischer Restsatz