Chinesischer Restsatz Rechner: Modulare Systeme Schritt für Schritt lösen
Ein Chinesischer-Restsatz-Rechner löst ein System von simultanen Kongruenzen – Aussagen wie x ≡ 2 (mod 3) und x ≡ 3 (mod 5) – indem er sie in eine einzelne Kongruenz modulo des Produkts (oder des kleinsten gemeinsamen Vielfachen) der einzelnen Moduli kombiniert. Die Methode stammt aus etwa 1.500 Jahren zurück und findet sich im chinesischen mathematischen Text Sunzi Suanjing, und heute unterstützt sie RSA-Kryptographie-Optimierungen, Kalenderberechnungen und fehlerkorrigierende Codes, zusätzlich dazu, dass sie ein Grundpfeiler der Diskreten Mathematik und Zahlentheorie-Kurse ist. Diese Anleitung erklärt, wie der Rechner intern funktioniert, wie man überprüft, ob ein System überhaupt eine Lösung hat, wie man die modularen Inversen findet, auf denen die Methode basiert, zwei vollständig durchgerechnete Beispiele – eines mit paarweise teilerfremden Moduli und eines ohne – sowie häufige Fehler und Übungsaufgaben.
Inhalt
- 01Was ist der Chinesische Restsatz?
- 02Wie funktioniert ein Chinesischer-Restsatz-Rechner?
- 03Wie überprüfst du, ob Moduli kompatibel sind?
- 04Was ist ein modularer Inverser und wie findet man ihn?
- 05Durchgerechnetes Beispiel: Lösen von paarweise teilerfremd Kongruenzen
- 06Durchgerechnetes Beispiel: Abstimmung von nicht-teilerfremd Moduli
- 07Rekonstruktion der kleinsten nichtnegativen Lösung
- 08Was sind die häufigsten Chinesischen-Restsatz-Fehler?
- 09Übungsaufgaben: Teste deine Chinesischer-Restsatz-Rechner-Fähigkeiten
Was ist der Chinesische Restsatz?
Der Chinesische Restsatz (CRT) besagt, dass Sie, wenn Sie ein System von Kongruenzen x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ) haben, und die Moduli m₁, m₂, ..., mₙ paarweise teilerfremd sind (jedes Paar hat keinen gemeinsamen Faktor außer 1), dann genau eine Lösung für x modulo M gibt, wobei M = m₁ × m₂ × ... × mₙ. Der Satz verdankt seinen Namen seinem frühesten bekannten Erscheinen im chinesischen Text des 3. bis 5. Jahrhunderts Sunzi Suanjing (Sun Zis Rechenbuch), die das jetzt klassische Rätsel stellte: Finde eine Zahl, die beim Teilen durch 3 den Rest 2 lässt, beim Teilen durch 5 den Rest 3 und beim Teilen durch 7 den Rest 2. Dieses Rätsel – und die CRT-Methode, die es löst – erscheint ständig außerhalb des Klassenzimmers: RSA-Kryptographie nutzt CRT, um die Entschlüsselung zu beschleunigen, indem mit kleineren Moduli statt einem riesigen gearbeitet wird, Informatiker verwenden es, um große Zahlen als Tupel kleinerer Reste für schnellere Arithmetik darzustellen, und Kalendersysteme verwenden es, um Zyklen unterschiedlicher Längen abzustimmen (Wochentage, Tage des Monats und Schaltjahrzyklen).
Chinesischer Restsatz: Für paarweise teilerfremde Moduli m₁, ..., mₙ hat das System x ≡ aᵢ (mod mᵢ) genau eine Lösung modulo M = m₁ × m₂ × ... × mₙ.
Wie funktioniert ein Chinesischer-Restsatz-Rechner?
Ein Chinesischer-Restsatz-Rechner automatisiert vier Schritte, die von Hand zu verfolgen sind, besonders wenn ein System drei oder mehr Kongruenzen hat, besonders die Berechnungen modularer Inverse. Intern behandelt er jede Kongruenz als ein Paar (aᵢ, mᵢ), bestätigt, dass die Moduli zusammen nutzbar sind, und konstruiert dann die eindeutige Lösung mit einer gewichteten Summe statt durch Ausprobieren. Das Verständnis dieser vier Schritte ermöglicht es dir, die Ausgabe eines Rechners zu überprüfen oder das gleiche Problem von Hand zu lösen, wenn in einer Prüfung kein Rechner erlaubt ist.
1. Schritt 1: Überprüfe die Moduli
Bestätige, dass jedes Paar von Moduli teilerfremd ist (gcd = 1). Wenn ein Paar einen gemeinsamen Faktor hat, wechselt der Rechner zur Kompatibilitätsprüfung im nächsten Abschnitt, statt die Standardformel zu verwenden.
2. Schritt 2: Berechne den kombinierten Modulus M
Multipliziere alle Moduli zusammen: M = m₁ × m₂ × ... × mₙ. Dies ist der Modulus der endgültigen, kombinierten Antwort.
3. Schritt 3: Finde jeden partiellen Quotient und seinen modularen Inversen
Für jede Kongruenz i, berechne Mᵢ = M / mᵢ (das Produkt aller Moduli außer mᵢ), dann finde den modularen Inversen von Mᵢ modulo mᵢ – nenne ihn yᵢ, wobei Mᵢ × yᵢ ≡ 1 (mod mᵢ).
4. Schritt 4: Kombinieren und reduzieren
Summiere aᵢ × Mᵢ × yᵢ über jede Kongruenz, dann reduziere diese Summe modulo M, um die eindeutig kleinste nichtnegative Lösung x zu erhalten.
Die Formel hinter jedem Chinesischen-Restsatz-Rechner: x ≡ Σ (aᵢ × Mᵢ × yᵢ) mod M, wobei Mᵢ = M/mᵢ und yᵢ der modulare Inverse von Mᵢ mod mᵢ ist.
Wie überprüfst du, ob Moduli kompatibel sind?
Die Lehrbuchversion des Chinesischen Restsatzes erfordert paarweise teilerfremde Moduli, aber echte Systeme – besonders solche, die in Planungs- oder Kryptographie-Problemen auftauchen – haben oft Moduli, die Faktoren teilen. Eine verallgemeinerte Version von CRT gilt immer noch, aber nur wenn das System zuerst eine Kompatibilitätsprüfung besteht: Für jedes Paar von Kongruenzen x ≡ aᵢ (mod mᵢ) und x ≡ aⱼ (mod mⱼ) müssen die beiden in der Überlappung zustimmen, was bedeutet aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ)). Wenn diese Überprüfung auch nur für ein Paar fehlschlägt, hat das System überhaupt keine Lösung – und ein guter Rechner meldet dies, statt eine falsche Zahl zu liefern.
1. Schritt 1: Berechne gcd(mᵢ, mⱼ) für jedes Paar von Moduli
Für ein Zwei-Kongruenzen-System gibt es nur ein Paar zu überprüfen. Für ein Drei-Kongruenzen-System überprüfe alle drei Paare.
2. Schritt 2: Reduziere beide Reste modulo dieser gcd
Nimm aᵢ mod gcd(mᵢ, mⱼ) und aⱼ mod gcd(mᵢ, mⱼ). Wenn sie übereinstimmen, ist das Paar kompatibel.
3. Schritt 3: Beispiel eines inkompatiblen Systems
Nimm x ≡ 1 (mod 4) und x ≡ 0 (mod 6). gcd(4, 6) = 2. Reduziere: 1 mod 2 = 1, und 0 mod 2 = 0. Da 1 ≠ 0, erfüllt keine ganze Zahl beide Kongruenzen – das System hat keine Lösung, und ein Chinesischer-Restsatz-Rechner sollte genau das melden, statt eine Antwort zu erzwingen.
Kompatibilitätsregel für nicht-teilerfremde Moduli: x ≡ aᵢ (mod mᵢ) und x ≡ aⱼ (mod mⱼ) können beide wahr sein, nur wenn aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ)).
Was ist ein modularer Inverser und wie findet man ihn?
Der modulare Inverse einer Zahl a modulo m ist eine andere Zahl b, so dass a × b ≡ 1 (mod m) – sie spielt die gleiche Rolle wie 1/a bei gewöhnlicher Division, aber beschränkt auf ganze Zahlen innerhalb eines festen Modulus. Ein modularer Inverser existiert genau dann, wenn gcd(a, m) = 1, was genau der Grund ist, warum der Standard-Chinesische Restsatz teilerfremde Moduli erfordert: Es garantiert, dass jeder Mᵢ einen Inversen mod mᵢ hat. Der zuverlässigste Weg, einen modularen Inversen von Hand zu finden, ist der erweiterte Euklidische Algorithmus, der den gewöhnlichen gcd-Algorithmus vorwärts läuft und dann rückwärts arbeitet, um 1 als eine Kombination von a und m auszudrücken.
1. Schritt 1: Führe den Euklidischen Algorithmus vorwärts aus
Finde den Inversen von 4 mod 7. Teile wiederholt: 7 = 1×4 + 3, dann 4 = 1×3 + 1, dann 3 = 3×1 + 0. Die Reste sind 3, dann 1, dann 0, was bestätigt, dass gcd(4, 7) = 1, daher existiert ein Inverser.
2. Schritt 2: Arbeite rückwärts, um 1 zu isolieren
Aus der zweitletzten Zeile: 1 = 4 − 1×3. Ersetze 3 = 7 − 1×4 aus der ersten Zeile: 1 = 4 − 1×(7 − 1×4) = 2×4 − 1×7.
3. Schritt 3: Lese den Inversen ab
Die Gleichung 1 = 2×4 − 1×7 bedeutet 2×4 ≡ 1 (mod 7), also ist der Inverse von 4 mod 7 gleich 2. Schnelle Überprüfung: 4 × 2 = 8 = 7 + 1, was wirklich ≡ 1 (mod 7) ist.
Für kleine Moduli ist es oft schneller, Kandidaten direkt zu testen: Multipliziere a mit 1, 2, 3, ... mod m, bis das Produkt 1 ist. Für größere Moduli ist der erweiterte Euklidische Algorithmus viel zuverlässiger.
Durchgerechnetes Beispiel: Lösen von paarweise teilerfremd Kongruenzen
Das ist das klassische Problem aus Sunzi Suanjing: Finde x so dass x ≡ 2 (mod 3), x ≡ 3 (mod 5) und x ≡ 2 (mod 7). Die Moduli 3, 5 und 7 sind paarweise teilerfremd, daher gilt die Standard-CRT-Formel direkt.
1. Schritt 1: Berechne M
M = 3 × 5 × 7 = 105.
2. Schritt 2: Berechne jedes Mᵢ und seinen Inversen
M₁ = 105/3 = 35. 35 mod 3 = 2, und der Inverse von 2 mod 3 ist 2 (da 2×2 = 4 ≡ 1 mod 3). M₂ = 105/5 = 21. 21 mod 5 = 1, und der Inverse von 1 mod 5 ist 1. M₃ = 105/7 = 15. 15 mod 7 = 1, und der Inverse von 1 mod 7 ist 1.
3. Schritt 3: Kombinieren
x ≡ (a₁×M₁×y₁) + (a₂×M₂×y₂) + (a₃×M₃×y₃) mod M = (2×35×2) + (3×21×1) + (2×15×1) mod 105 = 140 + 63 + 30 mod 105 = 233 mod 105 = 23.
4. Schritt 4: Überprüfe
23 ÷ 3 = 7 Rest 2 ✓. 23 ÷ 5 = 4 Rest 3 ✓. 23 ÷ 7 = 3 Rest 2 ✓. Die kleinste nichtnegative Lösung ist x = 23, und jede andere Lösung ist 23 + 105k für jede ganze Zahl k.
x ≡ 23 (mod 105) – die gleiche Antwort, die ein Chinesischer-Restsatz-Rechner sofort zurückgibt, und das gleiche Rätsel, das vor über tausend Jahren diesen Zweig der Zahlentheorie eröffnete.
Durchgerechnetes Beispiel: Abstimmung von nicht-teilerfremd Moduli
Löse nun x ≡ 3 (mod 4) und x ≡ 1 (mod 6), wobei 4 und 6 nicht teilerfremd sind (sie teilen einen Faktor von 2). Die Standardformel aus dem paarweise-teilerfremd Beispiel gilt nicht direkt, aber das System kann immer noch eine eindeutige Lösung modulo des kleinsten gemeinsamen Vielfachen der Moduli haben, vorausgesetzt, es besteht zuerst die Kompatibilitätsprüfung.
1. Schritt 1: Überprüfe Kompatibilität
gcd(4, 6) = 2. Reduziere beide Reste: 3 mod 2 = 1, und 1 mod 2 = 1. Sie stimmen überein, daher ist das System kompatibel und eine Lösung existiert.
2. Schritt 2: Finde den kombinierten Modulus
Statt 4 × 6 = 24 zu multiplizieren, verwende das kleinste gemeinsame Vielfache: lcm(4, 6) = 12. Die Lösung wird eindeutig modulo 12 sein, nicht 24.
3. Schritt 3: Ersetze und löse
Schreibe x = 4k + 3 aus der ersten Kongruenz, dann ersetze in die zweite: 4k + 3 ≡ 1 (mod 6), also 4k ≡ −2 ≡ 4 (mod 6). Beide Seiten und der Modulus teilen einen Faktor von gcd(4, 6) = 2, also teile die gesamte Kongruenz durch 2: 2k ≡ 2 (mod 3). Der Inverse von 2 mod 3 ist 2, also k ≡ 2×2 ≡ 1 (mod 3).
4. Schritt 4: Rekonstruiere x
k = 3j + 1 für jede ganze Zahl j, also x = 4(3j + 1) + 3 = 12j + 7. Die kleinste nichtnegative Lösung ist x = 7.
5. Schritt 5: Überprüfe
7 mod 4 = 3 ✓. 7 mod 6 = 1 ✓. So x ≡ 7 (mod 12) ist korrekt, und die Kongruenz durch den gemeinsamen Faktor zu teilen – statt ihn zu ignorieren – ist der Schritt, der nicht-teilerfremd CRT zum Funktionieren bringt.
Wenn Moduli einen gemeinsamen Faktor teilen, kannst du die paarweise-teilerfremd Formel nicht einfach so verwenden – du musst die resultierende Kongruenz durch gcd(mᵢ, mⱼ) teilen, bevor du den Inversen findest, sonst existiert der Inverse nicht.
Rekonstruktion der kleinsten nichtnegativen Lösung
Jedes Chinesisches-Restsatz-System, das seine Kompatibilitätsprüfung besteht, hat unendlich viele Ganzzahllösungen, nicht nur eine – aber sie sind alle zueinander kongruent modulo M (oder modulo lcm(m₁, ..., mₙ) im nicht-teilerfremd Fall). Nach Konvention meldet ein Rechner den kleinsten nichtnegativen Vertreter dieser unendlichen Familie, den Wert x₀, der 0 ≤ x₀ < M erfüllt, weil es die einzige kanonische Antwort ist, die am einfachsten zu formulieren, vergleichen und überprüfen ist. Jede andere Lösung ist einfach x₀ plus oder minus ein Vielfaches von M.
1. Reduktion einer negativen Zwischensumme
Die gewichtete Summe in Schritt 4 der Rechner-Methode kann negativ werden, wenn ein Rest aᵢ negativ ist oder wenn ein modularer Inverser als negativer Vertreter berechnet wurde. Wenn die Summe z.B. S = −37 ist und M = 45, addiere M wiederholt, bis das Ergebnis nichtnegativ ist: −37 + 45 = 8, daher ist die kleinste nichtnegative Lösung x₀ = 8, nicht −37.
2. Die vollständige Lösungsmenge
Sobald du x₀ hast, ist die vollständige Lösungsmenge jede Ganzzahl der Form x₀ + kM für k = ..., −2, −1, 0, 1, 2, .... Im Sunzi-Beispiel oben sind das 23, 128, 233, ... und auch −82, −187, und so weiter – aber 23 ist der, den du meldest, wenn nicht ein spezifischer Bereich angefordert wird.
Ein negatives oder übergroßes Zwischenergebnis ist nicht falsch – es wurde einfach noch nicht reduziert. Addiere oder subtrahiere Vielfache von M, bis der Wert in [0, M) liegt.
Was sind die häufigsten Chinesischen-Restsatz-Fehler?
Die meisten Fehler in CRT-Problemen entstehen durch das Auslassen einer Überprüfung statt durch eine fehlerhafte letzte Berechnung, weshalb es sich lohnt, am Anfang eines Problems langsamer zu machen statt am Ende.
1. Anwendung der teilerfremd Formel auf nicht-teilerfremd Moduli
Wenn zwei Moduli einen Faktor teilen, führt die Berechnung von M als ihr Straight-Produkt und die Suche nach modularen Inversen auf die Standard-Weise zu Fehlschlag oder zu einer falschen Antwort – überprüfe immer zuerst gcd(mᵢ, mⱼ) = 1 für jedes Paar.
2. Verwechslung eines modularen Inversen mit einem gewöhnlichen Reziproken
Der Inverse von 4 mod 7 ist 2, nicht 1/4 – modulare Inverse sind Ganzzahlen, die über den erweiterten Euklidischen Algorithmus gefunden werden (oder Ausprobieren für kleine Moduli), nie Brüche.
3. Falsche Reduktion negativer Zahlen modulo m
−2 mod 6 ist 4, nicht −2 und nicht 2 – addiere weiterhin den Modulus, bis das Ergebnis im Bereich [0, m) liegt. Abschneiden oder den Absolutwert nehmen statt den Modulus zu addieren, ist eine häufige Quelle falscher Antworten.
4. Vergessen, durch den gemeinsamen Faktor in nicht-teilerfremd Systemen zu teilen
Wenn Moduli einen gemeinsamen Faktor teilen, muss eine Kongruenz wie 4k ≡ 4 (mod 6) durch gcd(4, 6) = 2 geteilt werden, um zu 2k ≡ 2 (mod 3) zu werden, bevor du einen Inversen findest – 4 hat überhaupt keinen Inversen mod 6, da gcd(4, 6) ≠ 1.
5. Stoppen, bevor man die endgültige Summe modulo M reduziert
Die gewichtete Summe aus Schritt 4 (z.B. 233 im Sunzi-Problem) ist nicht die endgültige Antwort – sie muss modulo M reduziert werden (233 mod 105 = 23), um die kleinste nichtnegative Lösung zu erreichen.
Wenn deine Antwort nicht jede ursprüngliche Kongruenz erfüllt, wenn du sie wieder einsetzt, überprüfe zuerst die Kompatibilitätsprüfung und die modularen Inverse – das ist, wo fast jeder CRT-Fehler wirklich passiert.
Übungsaufgaben: Teste deine Chinesischer-Restsatz-Rechner-Fähigkeiten
Arbeite durch diese drei Systeme von Hand, überprüfe paarweise Teilerfremdheit oder Kompatibilität zuerst, bevor du die Lösungen unten vergleichst. Das zweite Problem ist absichtlich unlösbar – das zu erkennen ist genauso wichtig wie eine numerische Antwort zu finden, wenn es existiert.
1. Aufgabe 1 (paarweise teilerfremd)
Löse: x ≡ 1 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7). Antwort: M = 105. M₁ = 35 mit Inversem 2 mod 3; M₂ = 21 mit Inversem 1 mod 5; M₃ = 15 mit Inversem 1 mod 7. Summe = (1×35×2) + (4×21×1) + (6×15×1) = 70 + 84 + 90 = 244. 244 mod 105 = 34. Überprüfung: 34 mod 3 = 1 ✓, 34 mod 5 = 4 ✓, 34 mod 7 = 6 ✓. Lösung: x ≡ 34 (mod 105).
2. Aufgabe 2 (inkompatible Moduli – keine Lösung)
Löse: x ≡ 2 (mod 8), x ≡ 5 (mod 12). gcd(8, 12) = 4. Reduziere: 2 mod 4 = 2, und 5 mod 4 = 1. Da 2 ≠ 1, ist das System inkompatibel und hat keine Lösung – ein Chinesischer-Restsatz-Rechner sollte diese Schlussfolgerung zurückgeben statt einer unkorrekten Zahl.
3. Aufgabe 3 (kompatible nicht-teilerfremd Moduli)
Löse: x ≡ 5 (mod 9), x ≡ 2 (mod 6). gcd(9, 6) = 3. Reduziere: 5 mod 3 = 2, und 2 mod 3 = 2 – kompatibel. lcm(9, 6) = 18. Schreibe x = 9k + 5, ersetze: 9k + 5 ≡ 2 (mod 6) → 9k ≡ −3 ≡ 3 (mod 6). Teile durch gcd(9, 6) = 3: 3k ≡ 1 (mod 2) → k ≡ 1 (mod 2). Also k = 2j + 1, was x = 9(2j+1) + 5 = 18j + 14 ergibt. Überprüfung: 14 mod 9 = 5 ✓, 14 mod 6 = 2 ✓. Lösung: x ≡ 14 (mod 18). Wenn du jeden modularen Inversen und Reduktionsschritt in einem Problem wie diesem überprüfen möchtest, wird dir Solvifys Schritt-für-Schritt Math-Löser jeden Schritt genauso durchgehen wie diese Anleitung.
Der schnellste Weg, echte Vertrautheit mit dem Chinesischen Restsatz zu entwickeln, ist, eine Mischung aus teilerfremd, nicht-teilerfremd-aber-kompatibel und inkompatiblen Systemen zu lösen – zu erkennen, welche Fall du hast, ist die halbe Fähigkeit.
Verwandte Artikel
Restsatz-Rechner: Wie man Reste Schritt für Schritt findet
Ein anderes, aber verwandtes Rest-Konzept – dieser Leitfaden behandelt den Polynomial-Restsatz, nützlicher Kontext vor der Bewältigung modularerer Kongruenzen.
Gauß-Eliminierungs-Rechner: Löse lineare Systeme Schritt für Schritt
Eine andere systematische, algorithmus-gesteuerte Rechner-Methode – vergleiche, wie Gauß-Eliminierung und der Chinesische Restsatz jeweils ein System auf eine einzelne Antwort reduzieren.
Schritt-für-Schritt Mathematikproblem-Lösung: Ein wiederholbarer Rahmen für jedes Problem
Der 5-Schritte-Rahmen in diesem Leitfaden gilt direkt auf CRT-Probleme an: Identifiziere, was gegeben ist, wähle eine Methode, arbeite systematisch, und überprüfe das Ergebnis.
Verwandte Mathe-Löser
Smart Scan Solver
Mache ein Foto eines Kongruenzsystems oder Zahlentheorie-Problems und erhalte eine sofortige Schritt-für-Schritt-Lösung des Chinesischen Restsatzes.
Schritt-für-Schritt-Lösungen
Siehe jeden modularen Inversen, jede Kompatibilitätsprüfung und jeden Reduktionsschritt erklärt, nicht nur das endgültige Residuum.
KI-Math-Tutor
Stelle Folgefragen zu modularen Inversen, teilerfremden Moduli oder warum ein System keine Lösung hat, mit Antworten, die auf dein genaues Problem zugeschnitten sind.
Verwandte Fächer
Algebra-Grundlagen
Vertrautheit mit Brüchen und Resten macht modulare Arithmetik und den Chinesischen Restsatz viel einfacher zu erlernen.
Matrix-Rang-Rechner
Eine weitere zahlentheorie-ähnliche, algorithmus-gesteuerte Rechner-Methode – nützliche Übung für die gleiche systematische, Schritt-für-Schritt-Denkweise, die CRT erfordert.