Rechner zum chinesischen Restsatz

Lösen Sie drei gleichzeitige Kongruenzen mit paarweise teilerfremden Moduln.

Kongruenzsystem lösen

Geben Sie jeden ganzzahligen Rest neben seinem positiven Modul ein.

Rest 1

Modul 1

Rest 2

Modul 2

Rest 3

Modul 3

Über den Rechner zum chinesischen Restsatz

Der chinesische Restsatz, häufig mit CRT abgekürzt, verbindet mehrere modulare Bedingungen zu einer Lösung. Eine Kongruenz wie x ≡ 2 modulo 3 bedeutet, dass bei der Division von x durch 3 der Rest 2 bleibt. Dieser Rechner nimmt drei solche Gleichungen entgegen und findet die kleinste nichtnegative ganze Zahl, die alle zugleich erfüllt. Der klassische Satz gilt für paarweise teilerfremde Moduln, also wenn jedes Paar den größten gemeinsamen Teiler eins hat. Dann gibt es genau eine Lösung modulo dem Produkt der Moduln. Bei den Moduln 3, 5 und 7 beträgt das Produkt 105. Ist die kleinste Lösung 23, erfüllen auch 23, 128, 233 und alle durch wiederholtes Addieren oder Subtrahieren von 105 entstehenden Zahlen dasselbe System. Der konstruktive Algorithmus multipliziert zunächst alle Moduln zu M. Für jede Gleichung teilt er M durch deren Modul und bildet so ein Teilprodukt. Weil die Moduln paarweise teilerfremd sind, besitzt dieses Teilprodukt ein multiplikatives Inverses modulo dem ausgelassenen Modul. Das Produkt aus Rest, Teilprodukt und Inversen ergibt einen Term, der eine Kongruenz erfüllt und zu den übrigen null beiträgt. Die Summe dieser Terme wird modulo M reduziert und liefert die Antwort. Der CRT hat Anwendungen weit über die Zahlentheorie im Lehrbuch hinaus. Er unterstützt effiziente Arithmetik großer Ganzzahlen, kryptografische Implementierungen, Codierungstheorie, Kalenderzyklen, rotierende Dienstpläne, Computeralgebra und die Rekonstruktion von Werten aus Resten. Besonders nützlich ist er, wenn sich eine schwierige Berechnung in kleinere unabhängige Rechnungen modulo mehrerer Zahlen zerlegen und anschließend wieder zusammensetzen lässt. Geben Sie ganzzahlige Reste und Moduln größer als eins ein. Ein Rest darf negativ oder größer als sein Modul sein, da die Reduktion ihn automatisch normalisiert. Diese Version verlangt bewusst paarweise teilerfremde Moduln, entsprechend dem Standardsatz und zur Sicherstellung einer eindeutigen Restklasse. Systeme mit nicht teilerfremden Moduln können manchmal gelöst werden, erfordern aber eine zusätzliche Verträglichkeitsprüfung und liegen außerhalb des Umfangs dieses Rechners. Prüfen Sie das Ergebnis stets durch Division durch jeden Modul und Vergleich der Reste.

Beispiele zum chinesischen Restsatz

Jede Zeile vereint drei Kongruenzen in einer Restklasse.

Kongruenzen	Lösung	Erklärung
2 mod 3; 3 mod 5; 2 mod 7	23 mod 105	Dreiundzwanzig liefert die drei geforderten Reste.
1 mod 4; 2 mod 5; 3 mod 7	17 mod 140	Das Produkt der paarweise teilerfremden Moduln ist 140.
0 mod 2; 1 mod 3; 4 mod 5	4 mod 30	Vier ist die kleinste nichtnegative gemeinsame Lösung.

So lösen Sie Kongruenzen

Geben Sie den ganzzahligen Rest und den Modul der ersten Kongruenz ein.
Geben Sie das zweite und dritte Rest-Modul-Paar ein.
Prüfen Sie, ob jedes Modulpaar den größten gemeinsamen Teiler eins hat.
Wählen Sie Kongruenzen lösen, um die eindeutige Restklasse zu bestimmen.
Prüfen Sie die Antwort durch Reduktion modulo jedem eingegebenen Modul.

Häufige Fragen zum chinesischen Restsatz

Was bedeutet paarweise teilerfremd?

Jedes Paar verschiedener Moduln muss den größten gemeinsamen Teiler eins besitzen. Die Moduln selbst müssen keine Primzahlen sein.

Warum gibt es unendlich viele Lösungen?

Der Satz bestimmt eine Restklasse modulo dem Produkt aller Moduln. Das Addieren eines beliebigen Vielfachen dieses Produkts erhält jeden Rest.

Darf ein Rest größer als sein Modul sein?

Ja, er wird auf einen gleichwertigen Standardrest reduziert. Zum Beispiel entspricht Rest acht modulo fünf dem Rest drei.

Sind negative Reste erlaubt?

Ja, negative Reste stellen gültige Restklassen dar und lassen sich normalisieren. Die angezeigte Antwort ist der kleinste nichtnegative Vertreter.

Was passiert bei nicht teilerfremden Moduln?

Eine Lösung kann nur existieren, wenn sich überlappende Kongruenzen verträglich sind. Dieser Rechner folgt dem klassischen Satz für paarweise teilerfremde Moduln und meldet solche Systeme als nicht unterstützt.

Wie prüfe ich die CRT-Lösung?

Teilen Sie die angezeigte Lösung durch jeden Modul und prüfen Sie den Rest. Jeder Rest muss der zugehörigen Eingabe nach modularer Reduktion entsprechen.