So nutzen Sie den Chinesischer Restsatz Rechner
Der Chinesischer Restsatz Rechner ist ein spezialisiertes mathematisches Werkzeug zur Lösung von Systemen simultaner linearer Kongruenzen. Jede Zeile im Rechner entspricht einer Gleichung der Form $x \equiv a_i \pmod{m_i}$. Mit diesem Online-Rechner ermitteln Sie im Handumdrehen die kleinste positive Lösung sowie die allgemeine Lösungsmenge.
- Reste und Moduln eingeben — Tragen Sie für jede Kongruenz den Rest $a_i$ und den Modul $m_i$ ein. Über die Schaltfläche »+ Kongruenz hinzufügen« können Sie beliebig viele Zeilen ergänzen.
- Teilerfremdheit überprüfen — Der Chinesischer Restsatz Rechner prüft automatisch, ob alle eingegebenen Moduln paarweise teilerfremd sind. Sollte ein gemeinsamer Teiler vorliegen, erhalten Sie einen Hinweis.
- Ergebnis und Rechenweg ablesen — Nach der Eingabe liefert das Tool sofort die minimale Lösung $x$, den Gesamtmodul $M$ sowie eine strukturierte Schritt-für-Schritt-Tabelle mit allen Zwischenwerten ($M_i$, $y_i$, $a_i M_i y_i$).
Über das Löschen-Symbol (✕) neben jeder Zeile lässt sich eine Kongruenz jederzeit wieder entfernen.
Mathematische Grundlagen & Formel
Der Chinesischer Restsatz Rechner implementiert das klassische Lösungsverfahren für simultane Kongruenzen:
Gegeben: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ)
Voraussetzung: ggT(mᵢ, mⱼ) = 1 für alle i ≠ j (paarweise teilerfremd)
Gesamtmodul: M = m₁ · m₂ · ... · mₙ
Teilprodukte: Mᵢ = M / mᵢ
Modulare Inverse: yᵢ ≡ (Mᵢ)⁻¹ (mod mᵢ) mit Mᵢ · yᵢ ≡ 1 (mod mᵢ)
Gesamtlösung: x = (Σ aᵢ · Mᵢ · yᵢ) mod M
Allgemeine Form: x ≡ r (mod M) bzw. x = r + k · M (k ∈ ℤ)| Variable | Bezeichnung | Mathematische Bedeutung |
|---|---|---|
| M | Gesamtmodul | Produkt sämtlicher Moduln ($m_1 \cdot m_2 \cdot \dots \cdot m_n$) |
| Mᵢ | Teilprodukt | Quotient aus Gesamtmodul $M$ und jeweiligem Einzelmodul $m_i$ |
| yᵢ | Modulares Inverses | Lösung der linearen Kongruenz $M_i \cdot y_i \equiv 1 \pmod{m_i}$ |
| x | Minimale Lösung | Eindeutige ganzzahlige Lösung im Bereich $0 \le x < M$ |
Um jedes modulare Inverse $y_i$ zuverlässig zu bestimmen, verwendet der Chinesischer Restsatz Rechner den erweiterten euklidischen Algorithmus (EEA). Dies stellt sicher, dass auch bei größeren Zahlenwerten mathematisch exakte Resultate erzielt werden.
Wichtige Voraussetzungen und Grenzen
- Positive Moduln: Alle Moduln $m_i$ müssen positive ganze Zahlen größer als 1 sein.
- Paarweise Teilerfremdheit: Der klassische Satz verlangt, dass $\text{ggT}(m_i, m_j) = 1$ für alle Paare $i \neq j$ gilt.
- Ganze Reste: Reste können beliebige ganze Zahlen sein; negative Reste werden automatisch in den Hauptrestbereich modulo $m_i$ überführt.
- Gültigkeitsbereich: Für extrem große Eingaben arbeitet der Chinesischer Restsatz Rechner im sicheren Ganzzahlbereich von JavaScript ($2^{53} - 1$).
Schritt-für-Schritt-Beispielrechnung
Betrachten wir ein klassisches Kongruenzensystem, das sich mit dem Chinesischer Restsatz Rechner lösen lässt:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)- Gesamtmodul berechnen: $M = 3 \cdot 5 \cdot 7 = 105$. Da 3, 5 und 7 Primzahlen sind, sind sie paarweise teilerfremd.
- Teilprodukte ermitteln:
- $M_1 = 105 / 3 = 35$
- $M_2 = 105 / 5 = 21$
- $M_3 = 105 / 7 = 15$
- Modulare Inverse bestimmen:
- $35 \cdot y_1 \equiv 1 \pmod 3 \implies 2 \cdot y_1 \equiv 1 \pmod 3 \implies y_1 = 2$
- $21 \cdot y_2 \equiv 1 \pmod 5 \implies 1 \cdot y_2 \equiv 1 \pmod 5 \implies y_2 = 1$
- $15 \cdot y_3 \equiv 1 \pmod 7 \implies 1 \cdot y_3 \equiv 1 \pmod 7 \implies y_3 = 1$
- Gesamtsumme und Modulo bilden:
- $a_1 \cdot M_1 \cdot y_1 = 2 \cdot 35 \cdot 2 = 140$
- $a_2 \cdot M_2 \cdot y_2 = 3 \cdot 21 \cdot 1 = 63$
- $a_3 \cdot M_3 \cdot y_3 = 2 \cdot 15 \cdot 1 = 30$
- $\text{Summe} = 140 + 63 + 30 = 233$
- $x = 233 \bmod 105 = 23$
Das System ergibt somit die Lösung $x = 23$ und die allgemeine Lösungsform $x \equiv 23 \pmod{105}$.
Typische Anwendungsbereiche
Der Chinesischer Restsatz Rechner leistet in Theorie und Praxis wertvolle Hilfe:
- Zahlentheorie & Hochschulmathematik — Schnelles Überprüfen von Übungsaufgaben zur modularen Arithmetik und abstrakten Algebra.
- Kryptographie & RSA-Verfahren — Beschleunigung von Entschlüsselungsprozessen beim RSA-Algorithmus durch modulare Zerlegung großer Schlüssel (CRT-RSA).
- Informatik & Algorithmen — Verteilung von Berechnungen mit großen Ganzzahlen auf parallele Prozessoren mittels Restsystemen (Residue Number System, RNS).
- Kombinatorische Rätsel — Lösen historischer mathematischer Probleme, wie sie bereits im antiken China von Sun Zi formuliert wurden.
Mit dem interaktiven Chinesischer Restsatz Rechner erhalten Sie stets nachvollziehbare Zwischenschritte für Ihre mathematischen Aufgaben.