Du rechnest modulo der gewählten Moduli. Welche \(m_i\) gewählt werden ist prinzipiell egal, Solange diese p.w. teilerfremd sind. Dann ist der nachfolgende Schritt nämlich einfacher.
\(m_1\): \( 1010 \equiv 20 \mod (99)\) da 1010 bei Division durch 99 den Rest 20 lässt. Außerdem \( 997\equiv 7 \mod(99)\). 997 lässt bei Division durch 99 den Rest 7.
Insgesamt also \( 1010\cdot 997\equiv 20\cdot 7 \equiv 140 \equiv 41\mod(99)\)
Für die anderen Zahlen gleich vorgehen. Man erhält dann das System von linearen Kongruenzen:
$$ 1010\cdot 997\equiv 41\mod(99)\\1010\cdot 997\equiv 10\cdot(-3)\equiv -30\mod(100)\\1010\cdot 997\equiv 0\cdot(-13)\equiv0\mod(101)$$
Die Lösungen sind dann eindeutig modulo \( M:= \operatorname{kgV}(m_1,m_2,m_3)=99\cdot100\cdot101=999900\).Die Lösungsmenge ist also von der Form \( x + 999900\mathbb{Z}\).
Das x bestimmt man jetzt so: Setze \( M_i := M/m_i\) und berechne mit dem erweiterten Euklidischen Algorithmus Darstellungen der Form \( r_i m_i + s_i M_i = 1 \) (das geht, da die \( m_i\) p.w. teilerfremd sind, insb sind auch \(m_i\) und \( M_i\) teilerfremd für alle i, also \(\operatorname{ggT}(m_i,M_i)=1\)). Nun setzt man \( e_i := s_i M_i \). Dann ist
$$ x = 41e_1 -30e_2 +0e_3 = -19990930\equiv 7070\mod(999900)$$
Alternativ kann man auch \( e_i = M_i^{\varphi(m_i)}\) verwenden.
---
Man kann jetzt abschätzen, dass \( 1\cdot999900\le 1010\cdot 997 \le 2\cdot 999900\). Also muss \(1010\cdot 997=7070+1\cdot 999900\) sein. Hieraus kann man eine weitere Bedingung für die \( m_i\) ableiten: Sie sollten neben der Teilerfremdheit auch so gewählt werden, dass das kgV also M groß genug ist. Sonst muss man das Produkt herkömmlich ausrechnen. Wählt man für ein \( m_i \) außerdem einen Faktor des Produkts (hier 101) spart man sich später die Berechnung von gewissen \(e_i\).
Das ganze sieht jetzt zwar ziemlich hässlich aus und man fragt sich was das bringt. Ich habe diese Technik meines Wissens aber schon in der algorithmischen Algebra gesehen. Mit diesem "chinese remaindering" wird (erfolgreich) versucht effiziente und speichersparende Algorithmen für Problemstellungen in den ganzen Zahlen zu entwicklen.
