Die direkte CRT-Konstruktion

Der chinesische Restsatz · Abschnitt 38 von 64

Strategie

Einheitsgewichte bauen

Mit $M_i=M/m_i$ und $N_i=M_i^{-1}\pmod{m_i}$ ist $E_i=M_iN_i$ modulo $m_i$ gleich 1 und modulo jedem anderen $m_j$ gleich 0.

Formel

Eine Lösung ist $x_0=\sum_{i=1}^r a_iM_iN_i$ . Die vollständige Lösung lautet $x\equiv x_0\pmod M$ .

Gelöstes Beispiel

Für die Reste 2, 3, 2 modulo 3, 5, 7 ergibt die gewichtete Summe 233 und damit $x\equiv23\pmod{105}$ .

Checkliste