Chinesischer Restsatz Rechner

Willkommen beim Chinesischer Restsatz Rechner, einem leistungsstarken zahlentheoretischen Tool, das Systeme simultaner Kongruenzen mithilfe des Chinesischen Restsatzes (CRT) löst. Egal, ob Sie modulare Arithmetik studieren, sich auf Mathematikwettbewerbe vorbereiten, an Kryptographie-Problemen arbeiten oder Zahlentheorie erkunden – dieser Rechner bietet eine vollständige Schritt-für-Schritt-Lösung mit interaktiver Visualisierung, die zeigt, wie sich die Kongruenzklassen an der eindeutigen Lösung ausrichten.

Was ist der Chinesische Restsatz?

Der Chinesische Restsatz (CRT) ist ein grundlegendes Ergebnis der Zahlentheorie, das die Existenz und Eindeutigkeit einer Lösung für ein System simultaner Kongruenzen garantiert, vorausgesetzt, die Moduli sind paarweise teilerfremd. Der Satz wurde erstmals vom chinesischen Mathematiker Sunzi (孫子) in seinem Werk Sunzi Suanjing (孫子算經) etwa im 3. Jahrhundert n. Chr. beschrieben.

Formal gegeben ist das System:

Wenn alle Moduli \(m_1, m_2, \ldots, m_k\) paarweise teilerfremd sind (d. h. \(\gcd(m_i, m_j) = 1\) für alle \(i \neq j\)), dann existiert eine eindeutige Lösung \(x\) modulo \(M = m_1 \times m_2 \times \cdots \times m_k\).

Wie der CRT-Algorithmus funktioniert

Der konstruktive Beweis liefert den Algorithmus, den dieser Rechner verwendet:

Schritt 1: M berechnen

Berechnen Sie das Produkt aller Moduli:

Schritt 2: Jedes Mᵢ berechnen

Berechnen Sie für jede Kongruenz \(i\) den Wert \(M_i = M / m_i\). Dies ist das Produkt aller Moduli außer \(m_i\).

Schritt 3: Modulare Inverse finden

Finden Sie für jedes \(i\) ein \(y_i\), so dass \(M_i \cdot y_i \equiv 1 \pmod{m_i}\) gilt, unter Verwendung des erweiterten euklidischen Algorithmus. Da \(M_i\) und \(m_i\) teilerfremd sind (alle Moduli sind paarweise teilerfremd), existiert dieses Inverse immer.

Schritt 4: Die Lösung konstruieren

Die allgemeine Lösung ist \(x + k \cdot M\) für jede ganze Zahl \(k\), was bedeutet, dass sich die Lösung alle \(M\) Zahlen wiederholt.

So verwenden Sie diesen Rechner

1. Geben Sie Ihre Kongruenzen ein: Geben Sie für jede Gleichung \(x \equiv a \pmod{m}\) den Rest \(a\) und den Modulus \(m\) ein. Beginnen Sie mit 2 Kongruenzen und klicken Sie auf "Kongruenz hinzufügen" für weitere (bis zu 10).
2. Überprüfen Sie Ihre Moduli: Alle Moduli müssen positive ganze Zahlen ≥ 2 und paarweise teilerfremd sein. Der Rechner überprüft dies automatisch.
3. Klicken Sie auf "System lösen": Der Rechner wendet den CRT-Algorithmus an und zeigt die eindeutige Lösung zusammen mit dem Rechenweg an.
4. Prüfen Sie die Visualisierung: Der Zahlenstrahl zeigt, wie sich die Kongruenzklassen aus jeder Gleichung an der Lösung schneiden.
5. Verifizieren: Der Abschnitt zur Verifizierung bestätigt, dass die Lösung jede ursprüngliche Kongruenz erfüllt.

Die Ergebnisse verstehen

• Kleinste nicht-negative Lösung (x₀): Die eindeutige Lösung im Bereich [0, M−1]
• Allgemeine Lösung: Alle ganzen Zahlen der Form x₀ + kM, wobei k eine beliebige ganze Zahl ist
• Verifizierungstabelle: Bestätigt x₀ mod mᵢ = aᵢ für jede Kongruenz
• Schritt-für-Schritt-Aufschlüsselung: Zeigt Mᵢ, das modulare Inverse yᵢ und die Teilsumme aᵢ·Mᵢ·yᵢ für jede Gleichung
• Zahlenstrahl: Visuelle Darstellung, wie sich die Restklassen an der Lösung ausrichten

Anwendungen des Chinesischen Restsatzes

Das klassische Sunzi-Problem

Das ursprüngliche Problem aus Sunzi Suanjing fragt: "Es gibt gewisse Dinge, deren Anzahl unbekannt ist. Wenn wir sie zu dritt zählen, bleiben zwei übrig; zu fünft bleiben drei übrig; und zu siebt bleiben zwei übrig. Wie viele Dinge sind es?"

Dies übersetzt sich in: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\). Mit dem CRT ist die Antwort x = 23 (und allgemeiner 23 + 105k für jede nicht-negative ganze Zahl k).

Wann ist der CRT nicht anwendbar?

• Nicht teilerfremde Moduli: Wenn ein Paar von Moduli einen gemeinsamen Teiler größer als 1 hat, garantiert der Standard-CRT keine Lösung. Eine Lösung kann dennoch existieren, wenn die Reste kompatibel sind, aber dieser Rechner erfordert paarweise teilerfremde Moduli für den Standard-Algorithmus.
• Einzelne Kongruenz: Der CRT erfordert mindestens 2 Kongruenzen. Eine einzelne Kongruenz \(x \equiv a \pmod{m}\) hat bereits die triviale Lösung x = a.

Erweiterter euklidischer Algorithmus

Der erweiterte euklidische Algorithmus ist für den CRT unerlässlich, da er das modulare Inverse findet. Gegeben sind die ganzen Zahlen \(a\) und \(b\); er findet ganze Zahlen \(x\) und \(y\), so dass gilt:

Wenn \(\gcd(a, b) = 1\) ist, dann ist \(x\) das modulare Inverse von \(a\) modulo \(b\), d. h. \(a \cdot x \equiv 1 \pmod{b}\).

Häufig gestellte Fragen

Was ist der Chinesische Restsatz?

Der Chinesische Restsatz (CRT) besagt, dass ein System simultaner Kongruenzen x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ), bei dem alle Moduli paarweise teilerfremd sind, eine eindeutige Lösung modulo M = m₁ × m₂ × ... × mₖ besitzt. Dieser Satz wurde erstmals vom chinesischen Mathematiker Sunzi im 3. Jahrhundert beschrieben.

Was bedeutet paarweise teilerfremd?

Paarweise teilerfremd bedeutet, dass jedes Paar von Moduli keinen gemeinsamen Teiler außer 1 hat. Zum Beispiel sind {3, 5, 7} paarweise teilerfremd, da ggT(3,5)=1, ggT(3,7)=1 und ggT(5,7)=1. Jedoch sind {4, 6, 5} NICHT paarweise teilerfremd, da ggT(4,6)=2.

Wie löst man ein System von Kongruenzen Schritt für Schritt?

Zur Lösung mit dem CRT: (1) Überprüfen, ob alle Moduli paarweise teilerfremd sind. (2) M = Produkt aller Moduli berechnen. (3) Für jede Kongruenz Mᵢ = M/mᵢ berechnen. (4) Das modulare Inverse yᵢ von Mᵢ modulo mᵢ mit dem erweiterten euklidischen Algorithmus finden. (5) Die Lösung x = Σ(aᵢ × Mᵢ × yᵢ) mod M berechnen.

Was sind die Anwendungen des Chinesischen Restsatzes?

Der CRT hat viele praktische Anwendungen: Die RSA-Kryptographie nutzt ihn für eine effiziente Entschlüsselung. Die Informatik nutzt ihn für die Arithmetik mit großen Zahlen durch Zerlegung in modulare Teile. Signalverarbeitung nutzt den CRT in fehlerkorrigierenden Codes. Auch Planungs- und Kalenderprobleme nutzen den CRT.

Was passiert, wenn die Moduli nicht teilerfremd sind?

Wenn die Moduli nicht paarweise teilerfremd sind, ist der Standard-CRT nicht direkt anwendbar. In manchen Fällen existiert eine Lösung, wenn die Reste modulo des ggT der Moduli konsistent sind. Wenn keine Lösung existiert, ist das System inkonsistent.