Der chinesische Restsatz

Der chinesische Restsatz · Abschnitt 37 von 64

Intuition

Mehrere Koordinaten einer Zahl

Der chinesische Restsatz sagt: Bei teilerfremden Moduln gibt es genau eine Lösungsklasse. Und er gibt dir einen Bauplan, sie zu konstruieren.

Satz

Chinesischer Restsatz

Sind $m_1,\ldots,m_r$ paarweise teilerfremd, so besitzt jedes System $x\equiv a_i\pmod{m_i}$ eine Lösung. Sie ist eindeutig modulo $M=m_1\cdots m_r$ .

Beweis

Warum das Produkt die Eindeutigkeit liefert

Zwei Lösungen haben eine Differenz, die durch jedes $m_i$ teilbar ist. Wegen der paarweisen Teilerfremdheit teilt das Produkt $M$ diese Differenz.

Achtung

Paarweise statt nur insgesamt

Es genügt nicht, dass $\operatorname{ggT}(m_1,\ldots,m_r)=1$ ist. Jedes Paar muss ggT 1 besitzen, damit die direkte CRT-Form gilt.