Schrittweise und verallgemeinert

Der chinesische Restsatz · Abschnitt 39 von 64

Gelöstes Beispiel

Bedingungen nacheinander anfügen

Zwei Kongruenzen werden zuerst zu $x\equiv c\pmod L$ verbunden. Diese neue Klasse wird anschließend wie eine einzelne Kongruenz mit der nächsten Bedingung kombiniert.

Satz

Verallgemeinerte Form

Auch nicht paarweise teilerfremde Module können zusammengeführt werden. Ein System ist genau dann lösbar, wenn jedes Restpaar modulo des ggT seines Modulpaares übereinstimmt. Die Lösung ist dann eindeutig modulo des kgV aller Module.

Gelöstes Beispiel

Module sechs und neun

Die Bedingungen $x\equiv2\pmod6$ und $x\equiv5\pmod9$ sind kompatibel, weil die Reste modulo 3 übereinstimmen. Die Lösung lautet $x\equiv14\pmod{18}$ .

Entscheidungsweg

Welche Konstruktion?

1
Zwei Kongruenzen → Einsetzen ist meist am klarsten.
2
Viele kleine paarweise teilerfremde Module → direkte CRT-Summe.
3
Gemischte oder nicht teilerfremde Module → schrittweise zusammenführen und jedes Paar prüfen.
4
Nur Existenz gefragt → zuerst Verträglichkeitskriterium, Konstruktion eventuell unnötig.