Rechner für den Chinesischen Restsatz

Q: Wie kann ich ein CRT-System von Hand ohne die Formel lösen?

Bei zwei Kongruenzen können Sie Substitution verwenden: Nehmen Sie die erste, also x = a₁ + k·n₁ für ganze Zahlen k. Setzen Sie dies in die zweite Kongruenz ein, a_1 + k n_1 equiv a_2 ±odn_2, und lösen Sie nach k auf, indem Sie das Inverse von n_1 modulo n_2 bestimmen. Setzen Sie dann k zurück ein, um x zu erhalten, und reduzieren Sie modulo n_1 n_2. Diese Methode der sukzessiven Substitution funktioniert für beliebig viele Kongruenzen, indem immer je zwei auf einmal gelöst werden.

Q: Was passiert, wenn die Moduln nicht paarweise teilerfremd sind?

Wenn zwei Moduln einen gemeinsamen Teiler besitzen, kann das System inkonsistent sein und gar keine Lösung haben. Eine Lösung existiert nur, wenn die Reste verträglich sind: Für jedes Paar muss a_i equiv a_j ±odgcd(n_i, n_j) gelten. Sind sie verträglich, ist die Lösung weiterhin eindeutig, aber nur modulo dem kleinsten gemeinsamen Vielfachen der Moduln statt ihrem Produkt. Die Teilerfremdheitsbedingung garantiert, dass immer eine Lösung existiert — deshalb lehnt dieser Rechner solche Eingaben ab.

Q: Warum ist die Lösung eindeutig, und wie finde ich alle anderen Lösungen?

Die Eindeutigkeit folgt daraus, dass die Differenz zweier Zahlen x und x', die beide das System erfüllen, durch jeden Modul und damit durch ihr Produkt N teilbar ist (da sie teilerfremd sind). Also gilt x equiv x' ±odN, das heißt, es gibt genau eine Lösung in 0 ≤ x < N. Alle anderen Lösungen sind x + kN für jede ganze Zahl k, einschließlich negativer Werte wie x - N, falls Ihre Aufgabe dies zulässt.

Q: Können Reste negativ oder größer als der Modul sein?

Ja. Ein Rest, der größer als sein Modul ist, wird automatisch reduziert — zum Beispiel ist a = 7 mit n = 5 dasselbe wie a = 2. Auch negative Reste funktionieren: x equiv -1 ±od5 bedeutet dasselbe wie x equiv 4 ±od5. Das Endergebnis wird immer auf den kleinsten nicht-negativen Repräsentanten im Bereich 0 ≤ x < N normiert.

Q: Wie finde ich das modulare Inverse von Hand?

Verwenden Sie den erweiterten euklidischen Algorithmus: Führen Sie den gewöhnlichen euklidischen Algorithmus für N_i und n_i aus und arbeiten Sie dann rückwärts, um gcd = 1 als uN_i + vn_i darzustellen. Der Koeffizient u erfüllt uN_i equiv 1 ±odn_i, also y_i = u bmod n_i. Bei einem Primzahlmodul p können Sie auch den kleinen fermatschen Satz verwenden: y_i equiv N_i^p-2 ±odp.

Q: Welche häufigen Fehler treten bei der Anwendung des Chinesischen Restsatzes auf?

Die häufigsten Fehler sind: Moduln zu verwenden, die nicht paarweise teilerfremd sind (z. B. 4 und 6, die den Teiler 2 teilen); beim Eingeben die Felder für Rest und Modul zu verwechseln; zu vergessen, dass die Antwort eine ganze Lösungsklasse und keine einzelne Zahl ist; und einen Modul von 1 einzugeben, was zwar technisch erlaubt ist, aber keine Information hinzufügt. Prüfen Sie außerdem, ob Ihre Reste zur Aufgabe passen — x equiv 2 ±od3 ist nicht dasselbe wie x equiv 3 ±od2.

Q: Gibt es eine schnelle Möglichkeit, die Antwort des Rechners zu überprüfen?

Ja — teilen Sie die Antwort einfach durch jeden Modul und prüfen Sie die Reste. Wenn das Ergebnis x lautet, vergewissern Sie sich, dass x bmod n_i = a_i bmod n_i für jede Kongruenz Ihres Systems gilt. Eine zweite Kontrolle: Berechnen Sie x bmod N mit einer anderen Methode, etwa durch sukzessive Substitution, und bestätigen Sie, dass derselbe Wert herauskommt. Wenn beide Prüfungen bestanden sind, ist die Lösung korrekt, da die Eindeutigkeit modulo N garantiert, dass es im Bereich keine andere Antwort gibt.

Aktualisiert: 3 Oktober 2026

Löst ein System simultaner Kongruenzen mit dem Chinesischen Restsatz. Geben Sie die Reste und paarweise teilerfremden Moduln ein, um die kleinste nicht-negative Lösung zu erhalten.

Löser für den Chinesischen Restsatz

Formel des Chinesischen Restsatzes

Formel

\[ x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \\[1.5em] N = n_1 \cdot n_2 \cdots n_k, \quad N_i = \frac{N}{n_i}, \quad y_i \equiv N_i^{-1} \pmod{n_i} \\[1.5em] x \equiv \sum_{i=1}^{k} a_i \, N_i \, y_i \pmod{N} \]

Dabei gilt:

\(a_i\) — die Reste (die Werte, zu denen \(x\) kongruent sein muss)
\(n_i\) — die Moduln, die paarweise teilerfremd sein müssen (ihr größter gemeinsamer Teiler ist für je zwei von ihnen 1)
\(N\) — das Produkt aller Moduln, das bei Teilerfremdheit ihr kleinstes gemeinsames Vielfaches ist
\(N_i\) — das Produkt aller Moduln außer \(n_i\)
\(y_i\) — das multiplikative Inverse von \(N_i\) modulo \(n_i\), also die Zahl mit \(N_i y_i \equiv 1 \pmod{n_i}\)
\(x\) — die eindeutige Lösung modulo \(N\)

Der Satz besagt, dass das System bei paarweise teilerfremden Moduln genau eine Lösung im Bereich \(0 \le x < N\) besitzt. Die Formel konstruiert diese Lösung, indem jeder Rest mit dem Inverse des entsprechenden Teilprodukts kombiniert wird.

Chinesischer Restsatz – Rechenbeispiel

Beispiel: Gesucht ist \(x\) mit \(x \equiv 2 \pmod{3}\) und \(x \equiv 3 \pmod{5}\) — dies sind die Standardwerte des Rechners.

\[ N = 3 \times 5 = 15 \]

\[ N_1 = \frac{15}{3} = 5, \quad y_1 = 2 \; (\text{da } 5 \cdot 2 = 10 \equiv 1 \pmod{3}) \]

\[ N_2 = \frac{15}{5} = 3, \quad y_2 = 2 \; (\text{da } 3 \cdot 2 = 6 \equiv 1 \pmod{5}) \]

\[ x \equiv (2 \cdot 5 \cdot 2) + (3 \cdot 3 \cdot 2) \pmod{15} \equiv 20 + 18 = 38 \equiv 8 \pmod{15} \]

Ergebnis: \(x = 8\) modulo \(15\). Tatsächlich gilt \(8 \div 3 = 2\) Rest \(2\) und \(8 \div 5 = 1\) Rest \(3\), beide Kongruenzen sind also erfüllt. Die nächste Lösung ist \(8 + 15 = 23\), dann \(38\) und so weiter.

So benutzen Sie den Rechner

Geben Sie die Anzahl der Kongruenzen ein (mindestens 2). Weitere Rest-Modul-Paare erscheinen automatisch.
Geben Sie für die erste Kongruenz den Rest in Rest 1 (\(a_1\)) und den Modul in Modul 1 (\(n_1\)) ein.
Wiederholen Sie dies für Rest 2 / Modul 2 und alle weiteren Paare.
Lesen Sie die kleinste nicht-negative Lösung \(x\) und das Modulo (kgV der Moduln) \(N\) ab. Jede Zahl der Form \(x + kN\) (\(k = 0, 1, 2, \dots\)) erfüllt ebenfalls das System.

Was ist der Chinesische Restsatz?

Der Chinesische Restsatz (Chinese Remainder Theorem, CRT) ist ein klassisches Resultat der Zahlentheorie, das erstmals vom chinesischen Mathematiker Sunzi etwa im 3.–5. Jahrhundert n. Chr. beschrieben wurde. Er beantwortet die Frage: Wenn mehrere Teiler und die Reste bekannt sind, die bei der Division einer unbekannten Zahl durch jeden dieser Teiler übrig bleiben — lässt sich die Zahl dann rekonstruieren? Der Satz sagt ja — sofern die Moduln paarweise teilerfremd sind — und die Antwort ist eindeutig innerhalb eines Bereichs, dessen Länge das Produkt aller Moduln ist.

Ein anschauliches Bild: Wenn ein Eierkorb \(x\) Eier enthält und beim Abzählen zu je 3 ein Rest von 2 bleibt, beim Abzählen zu je 5 ein Rest von 3, dann gilt \(x \equiv 2 \pmod{3}\) und \(x \equiv 3 \pmod{5}\). Der CRT legt \(x\) eindeutig modulo 15 fest — in diesem Fall \(x = 8, 23, 38, \dots\)

Der Satz ist wichtig, weil er zeigt, dass ein System aus vielen kleinen Kongruenzen äquivalent zu einer einzigen Kongruenz mit einem großen Modul ist. So kann man Arithmetik mit einem riesigen Modul durch parallele Arithmetik mit mehreren kleinen, handlichen Moduln ersetzen und die Ergebnisse anschließend wieder zusammenfügen. Der Zusammenführungsschritt verwendet modulare Inverse, die Sie separat mit dem Rechner für das multiplikative Inverse modulo berechnen können; Inverse dieser Art hängen auch mit dem kleinen fermatschen Satz und dem Satz von Euler zusammen.

Interpretation des Ergebnisses

Der Rechner liefert die kleinste nicht-negative Lösung \(x\) und den kombinierten Modul \(N\). Die vollständige Lösungsmenge ist \(x, x + N, x + 2N, \dots\); wenn in Ihrer Aufgabe auch negative Antworten sinnvoll sind, funktionieren \(x - N\) und kleinere Werte ebenso. Da die Lösung modulo \(N\) eindeutig ist, beschreiben zwei verschiedene Eingaben, die dasselbe \(x \pmod{N}\) liefern, exakt dasselbe System.

Voraussetzungen und Grenzen

Paarweise teilerfremde Moduln sind erforderlich. Je zwei Moduln dürfen keinen gemeinsamen Teiler größer als 1 besitzen; andernfalls meldet der Rechner einen Fehler. Sind zwei Moduln z. B. 4 und 6 (beide durch 2 teilbar), kann das System gar keine Lösung haben oder mehrere Lösungen modulo ihrem kgV besitzen.
Konsistenz des Systems. Bei teilerfremden Moduln liefert der Satz stets eine Lösung — das ist die Stärke des CRT. Widersprüche zwischen Kongruenzen können nur auftreten, wenn die Teilerfremdheitsbedingung verletzt ist.
Reste dürfen den Modul überschreiten. Eine Eingabe wie \(a = 7, n = 5\) wird als \(7 \equiv 2 \pmod 5\) behandelt; der Rechner reduziert das Endergebnis automatisch modulo \(N\).
Moduln müssen positive ganze Zahlen sein. Werte von 0 oder negative Zahlen werden abgelehnt.
Große Systeme. Da \(N\) das Produkt aller Moduln ist, wächst es sehr schnell. Bei vielen Moduln können die beteiligten Zahlen den Bereich überschreiten, in dem die Standard-Gleitkommaarithmetik exakt arbeitet.

Wo der CRT verwendet wird

Über die reine Zahlentheorie hinaus ist der CRT ein praktisches Werkzeug in mehreren Gebieten. In der Kryptographie beschleunigt er die RSA-Entschlüsselung, indem das Ergebnis modulo jedem Primfaktor separat berechnet und wieder kombiniert wird; er ist auch die Grundlage von Schwellwertverfahren wie Shamir's Secret Sharing. In der Informatik ermöglicht er Restklassensysteme (Residue Number Systems), die Additionen und Multiplikationen parallel mit kleinen Moduln ausführen, und er taucht in Hashverfahren, Ablaufplanung und Kalenderrechnungen auf — die klassischen Probleme vom „Soldaten in Reihen zählen

Häufig gestellte Fragen

Wie kann ich ein CRT-System von Hand ohne die Formel lösen?

Bei zwei Kongruenzen können Sie Substitution verwenden: Nehmen Sie die erste, also x = a₁ + k·n₁ für ganze Zahlen \(k\). Setzen Sie dies in die zweite Kongruenz ein, \(a_1 + k n_1 \equiv a_2 \pmod{n_2}\), und lösen Sie nach \(k\) auf, indem Sie das Inverse von \(n_1\) modulo \(n_2\) bestimmen. Setzen Sie dann \(k\) zurück ein, um \(x\) zu erhalten, und reduzieren Sie modulo \(n_1 n_2\). Diese Methode der sukzessiven Substitution funktioniert für beliebig viele Kongruenzen, indem immer je zwei auf einmal gelöst werden.

Was passiert, wenn die Moduln nicht paarweise teilerfremd sind?

Wenn zwei Moduln einen gemeinsamen Teiler besitzen, kann das System inkonsistent sein und gar keine Lösung haben. Eine Lösung existiert nur, wenn die Reste verträglich sind: Für jedes Paar muss \(a_i \equiv a_j \pmod{\gcd(n_i, n_j)}\) gelten. Sind sie verträglich, ist die Lösung weiterhin eindeutig, aber nur modulo dem kleinsten gemeinsamen Vielfachen der Moduln statt ihrem Produkt. Die Teilerfremdheitsbedingung garantiert, dass immer eine Lösung existiert — deshalb lehnt dieser Rechner solche Eingaben ab.

Warum ist die Lösung eindeutig, und wie finde ich alle anderen Lösungen?

Die Eindeutigkeit folgt daraus, dass die Differenz zweier Zahlen \(x\) und \(x'\), die beide das System erfüllen, durch jeden Modul und damit durch ihr Produkt \(N\) teilbar ist (da sie teilerfremd sind). Also gilt \(x \equiv x' \pmod{N}\), das heißt, es gibt genau eine Lösung in \(0 \le x < N\). Alle anderen Lösungen sind \(x + kN\) für jede ganze Zahl \(k\), einschließlich negativer Werte wie \(x - N\), falls Ihre Aufgabe dies zulässt.

Können Reste negativ oder größer als der Modul sein?

Ja. Ein Rest, der größer als sein Modul ist, wird automatisch reduziert — zum Beispiel ist \(a = 7\) mit \(n = 5\) dasselbe wie \(a = 2\). Auch negative Reste funktionieren: \(x \equiv -1 \pmod{5}\) bedeutet dasselbe wie \(x \equiv 4 \pmod{5}\). Das Endergebnis wird immer auf den kleinsten nicht-negativen Repräsentanten im Bereich \(0 \le x < N\) normiert.

Wie finde ich das modulare Inverse von Hand?

Verwenden Sie den erweiterten euklidischen Algorithmus: Führen Sie den gewöhnlichen euklidischen Algorithmus für \(N_i\) und \(n_i\) aus und arbeiten Sie dann rückwärts, um \(\gcd = 1\) als \(uN_i + vn_i\) darzustellen. Der Koeffizient \(u\) erfüllt \(uN_i \equiv 1 \pmod{n_i}\), also \(y_i = u \bmod n_i\). Bei einem Primzahlmodul \(p\) können Sie auch den kleinen fermatschen Satz verwenden: \(y_i \equiv N_i^{p-2} \pmod{p}\).

Welche häufigen Fehler treten bei der Anwendung des Chinesischen Restsatzes auf?

Die häufigsten Fehler sind: Moduln zu verwenden, die nicht paarweise teilerfremd sind (z. B. 4 und 6, die den Teiler 2 teilen); beim Eingeben die Felder für Rest und Modul zu verwechseln; zu vergessen, dass die Antwort eine ganze Lösungsklasse und keine einzelne Zahl ist; und einen Modul von 1 einzugeben, was zwar technisch erlaubt ist, aber keine Information hinzufügt. Prüfen Sie außerdem, ob Ihre Reste zur Aufgabe passen — \(x \equiv 2 \pmod{3}\) ist nicht dasselbe wie \(x \equiv 3 \pmod{2}\).

Gibt es eine schnelle Möglichkeit, die Antwort des Rechners zu überprüfen?

Ja — teilen Sie die Antwort einfach durch jeden Modul und prüfen Sie die Reste. Wenn das Ergebnis \(x\) lautet, vergewissern Sie sich, dass \(x \bmod n_i = a_i \bmod n_i\) für jede Kongruenz Ihres Systems gilt. Eine zweite Kontrolle: Berechnen Sie \(x \bmod N\) mit einer anderen Methode, etwa durch sukzessive Substitution, und bestätigen Sie, dass derselbe Wert herauskommt. Wenn beide Prüfungen bestanden sind, ist die Lösung korrekt, da die Eindeutigkeit modulo \(N\) garantiert, dass es im Bereich keine andere Antwort gibt.