Rechnerwerk
Mathe & Formeln

Simultane Kongruenzen mit dem chinesischen Restsatz lösen

Geben Sie für jede Kongruenz den Rest a und den Modul m ein. Der Rechner findet die kleinste nichtnegative Zahl x, die alle Bedingungen gleichzeitig erfüllt.

Ihr Kongruenzsystem
Modul 1 eintragen, wenn Sie nur zwei Kongruenzen lösen möchten.
Ergebnis

Eine Zahl aus ihren Resten zurückgewinnen

Ein altes Rätsel aus dem chinesischen Mathematikbuch des Sunzi lautet sinngemäß: Eine Anzahl von Dingen lässt beim Zählen in Dreiern den Rest 2, in Fünfern den Rest 3 und in Siebenern den Rest 2. Wie viele sind es? Der chinesische Restsatz beantwortet solche Fragen allgemein. Sind die Moduln paarweise teilerfremd, gibt es genau eine Lösung zwischen 0 und dem Produkt der Moduln, und alle weiteren Lösungen entstehen durch Addition dieses Produkts.

Der Rechner löst bis zu drei Kongruenzen der Form x ≡ a mod m. Er arbeitet schrittweise: Zwei Kongruenzen werden zu einer zusammengefasst, die dann mit der nächsten kombiniert wird. Dazu bestimmt er mit dem erweiterten euklidischen Algorithmus ein modulares Inverses.

Auch Moduln mit gemeinsamen Teilern sind erlaubt. Dann ist das System nur lösbar, wenn sich die betroffenen Reste um ein Vielfaches des größten gemeinsamen Teilers unterscheiden. Ist das nicht der Fall, meldet der Rechner, welche Kongruenz den Widerspruch erzeugt. Die Lösung wiederholt sich in diesem Fall mit dem kleinsten gemeinsamen Vielfachen statt mit dem Produkt.

x ≡ a1 (mod m1) , x ≡ a2 (mod m2): x=a1+m1⋅tmit t ≡ (a2−a1)⋅(m1g)−1 (mod m2g)g , g=ggT (m1 , m2)x\,≡\,a_{1}\,\left(\text{mod m}_{1}\right)\,{,}\ x\,≡\,a_{2}\,\left(\text{mod m}_{2}\right):\ x = a_{1} + m_{1} \cdot t\quad \text{mit}\ \frac{t\,≡\,\left(a_{2} - a_{1}\right) \cdot \left(\frac{m_{1}}{g}\right)^{-1}\,\left(\frac{\text{mod m}_{2}}{g}\right)}{g}\,{,}\ g = \text{ggT}\,\left(m_{1}\,{,}\ m_{2}\right)

Beispiel: x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7: Die Moduln sind paarweise teilerfremd, ihr Produkt ist 105. Die kleinste Lösung ist x = 23, denn 23 = 7 · 3 + 2 = 4 · 5 + 3 = 3 · 7 + 2. Weitere Lösungen sind 128, 233 und 338.

Anwendungen und Hinweise zur Eingabe

In der Informatik beschleunigt der Restsatz Rechnungen mit großen Zahlen. Bei der RSA-Entschlüsselung rechnet man getrennt modulo der beiden Primfaktoren und setzt das Ergebnis anschließend zusammen, was spürbar schneller ist. Auch Kalenderrechnungen nutzen das Prinzip, etwa die Frage, wann mehrere Zyklen unterschiedlicher Länge wieder gleichzeitig beginnen.

Negative Reste sind erlaubt und werden intern in den Bereich von 0 bis m − 1 umgerechnet. x ≡ −1 mod 7 bedeutet dasselbe wie x ≡ 6 mod 7. Die Moduln sind auf eine Million begrenzt; die Rechnung selbst läuft mit ganzen Zahlen beliebiger Länge, damit keine Rundungsfehler entstehen.

Wenn Sie nur zwei Kongruenzen lösen möchten, tragen Sie beim dritten Modul eine 1 ein. Jede ganze Zahl lässt bei Division durch 1 den Rest 0, die Bedingung ist also immer erfüllt und verändert das Ergebnis nicht.

Zur Kontrolle teilen Sie die gefundene Lösung durch jeden Modul und vergleichen die Reste. Für den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache einzelner Zahlen eignet sich auch der ggT-kgV-Rechner.

Tipps und typische Fehler

Kongruenzen lösen.

  • Teilerfremd: Erst prüfen.
  • Negativ: Reste erlaubt.
  • Zwei: Dritten Modul 1.
  • Probe: Reste nachrechnen.

Weitere Rechner: Mathe & Formeln

Alle Rechner dieser Kategorie oder alle Rechner A–Z.

Häufige Fragen

Was besagt der chinesische Restsatz?

Bei paarweise teilerfremden Moduln hat ein System von Kongruenzen genau eine Lösung modulo dem Produkt der Moduln.

Ist ein System mit nicht teilerfremden Moduln lösbar?

Nur wenn sich die Reste jeweils um ein Vielfaches des ggT der Moduln unterscheiden.

Wie löse ich nur zwei Kongruenzen?

Für die dritte Kongruenz den Modul 1 eintragen.

Woher stammt der Name chinesischer Restsatz?

Aus einer Aufgabe im Rechenbuch des chinesischen Mathematikers Sunzi aus dem 3. bis 5. Jahrhundert.

Wie viele Lösungen hat ein Kongruenzsystem?

Unendlich viele, die sich jeweils um das kgV der Moduln unterscheiden.

Auch gesucht als:
  • chinesischer Restsatz
  • simultane Kongruenzen lösen
  • Kongruenzsystem lösen
  • chinesischer Restsatz Rechner
  • Restklassen System
  • x mod m Gleichungssystem

Alle Berechnungen erfolgen direkt in Ihrem Browser, Ihre Eingaben werden nicht übertragen oder gespeichert. Die Ergebnisse sind Orientierungswerte ohne Gewähr und ersetzen keine steuerliche, rechtliche oder finanzielle Beratung. Die Erklärtexte auf dieser Seite wurden mit KI erstellt. Letzte inhaltliche Änderung dieser Seite: . Mehr dazu: So entstehen und prüfen wir die Rechner.