Was ist der Chinesische Restsatz?

Er besagt, dass, wenn Sie die Reste einer unbekannten Ganzzahl x bei der Division durch mehrere paarweise teilerfremde Zahlen kennen, Sie x eindeutig modulo des Produkts dieser Zahlen bestimmen können.

Warum müssen die Moduli paarweise teilerfremd sein?

Die Garantie des Satzes für eine eindeutige Lösung modulo des Produkts gilt nur, wenn jedes Paar von Moduli keinen gemeinsamen Faktor teilt. Wenn zwei Moduli einen Faktor teilen, existiert entweder keine Lösung oder das System ist redundant, und die Standardkonstruktion des CRT gilt nicht.

Wie wird die Lösung konstruiert?

Für jede Kongruenz x ≡ aᵢ (mod mᵢ) berechnet der Algorithmus Mᵢ = M/mᵢ (wobei M das Produkt aller Moduli ist) und dessen modulares Inverses yᵢ mod mᵢ, summiert dann aᵢ×Mᵢ×yᵢ über alle Kongruenzen und reduziert modulo M.

Was bedeutet die Antwort 'x ≡ r (mod M)'?

Es bedeutet, dass jede Ganzzahl der Form r + k×M (für jede Ganzzahl k) alle ursprünglichen Kongruenzen gleichzeitig erfüllt — r ist einfach der kleinste nicht negative Repräsentant dieser Lösungsmenge.

Wie viele Kongruenzen kann ich eingeben?

Dieser Rechner unterstützt 2 bis 10 gleichzeitige Kongruenzen, was die überwiegende Mehrheit der praktischen CRT-Probleme abdeckt.

Was ist das klassische Beispiel im Stil 'drei Körbe', das dies löst?

Das klassische Rätsel 'finde eine Zahl, die bei Division durch 3 den Rest 2, bei Division durch 5 den Rest 3 und bei Division durch 7 den Rest 2 lässt' ist genau ein CRT-System mit 3 Kongruenzen, direkt mit diesem Rechner lösbar.

Wo wird CRT im echten Leben verwendet?

Er liegt der schnellen RSA-Entschlüsselung (CRT-RSA), der Computerarithmetik mit Restklassen-Zahlensystemen, Kalender- und Terminplanungsberechnungen sowie fehlerkorrigierenden Codes zugrunde.

Was passiert, wenn ein Modulus nicht teilerfremd mit einem anderen ist?

Der Rechner erkennt den gemeinsamen Faktor und meldet genau, welches Paar von Moduli in Konflikt steht, anstatt eine falsche oder unvollständige Lösung zurückzugeben.

Chinesischer Restsatz Rechner — Lösen Sie ein System von Kongruenzen

Unser Chinesischer-Restsatz-Rechner löst Systeme simultaner Kongruenzen — x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂) und so weiter — und findet die eindeutige Lösung modulo des Produkts der Moduli, sofern die Moduli paarweise teilerfremd sind. Er validiert die Teilerfremdheit im Voraus und berechnet die Lösung mit BigInt-Präzision.

Kurzantwort

Geben Sie jede Kongruenz als Rest,Modulus ein (eine pro Zeile, mindestens zwei Zeilen), um das System sofort für x über die konstruktive Methode des Chinesischen Restsatzes zu lösen.

Kongruenzen (Rest,Modulus pro Zeile)

Geben Sie mindestens zwei Kongruenzen ein, eine pro Zeile, z. B. 2,3 für x ≡ 2 (mod 3). Die Moduli müssen paarweise teilerfremd sein.

So verwenden Sie Chinesischer Restsatz Rechner — Lösen Sie Modulare Systeme

1
Geben Sie jede Kongruenz als "Rest,Modulus" in einer eigenen Zeile ein — mindestens zwei Zeilen.
2
Klicken Sie auf 'Berechnen', um das System für x zu lösen.
3
Sehen Sie sich den kombinierten Modulus und die schrittweise Konstruktion der Lösung an.

Warum Chinesischer Restsatz Rechner — Lösen Sie Modulare Systeme verwenden?

Der Chinesische Restsatz, erstmals vom chinesischen Mathematiker Sun Tzu um das 3. Jahrhundert n. Chr. aufgezeichnet, garantiert, dass ein System von Kongruenzen mit paarweise teilerfremden Moduli eine eindeutige Lösung modulo des Produkts dieser Moduli hat — und liefert eine explizite konstruktive Methode, um sie zu finden. Dieser Rechner validiert, dass Ihre Moduli tatsächlich paarweise teilerfremd sind (die Voraussetzung des Satzes), bevor die Kongruenzen über die Standardkonstruktion kombiniert werden, wobei das Teilprodukt und das modulare Inverse jedes Modulus verwendet werden.

Chinesischer Restsatz Rechner — Lösen Sie ein System von Kongruenzen

Kurzantwort

So verwenden Sie Chinesischer Restsatz Rechner — Lösen Sie Modulare Systeme

Warum Chinesischer Restsatz Rechner — Lösen Sie Modulare Systeme verwenden?

Häufig gestellte Fragen

Ähnliche Tools

Erweiterter Euklidischer Algorithmus Rechner — ggT + Bézout-Koeffizienten

Modulares Multiplikatives Inverses — Löse ax ≡ 1 (mod m) Online

Primitivwurzel-Rechner — Finden Sie einen Generator mod n