Chinesischer Restsatz Rechner
Lösen Sie simultane Kongruenzen in einem Schritt: x ≡ 2 (mod 3), x ≡ 3 (mod 5) und x ≡ 2 (mod 7) haben 23 als kleinste nichtnegative Lösung, und die Antwort wiederholt sich alle 105. Praktisch für Hausaufgaben, Wettbewerbe und Lösungsblätter. Kostenlos in Ihrem Browser.
- Kostenlos
- Läuft in Ihrem Browser
- Ohne Anmeldung
- Ihre Daten bleiben auf Ihrem Gerät
Im Browser ausführen – kostenlos
Rechenbeispiel
- Reste
- 2, 3, 2
- Moduln
- 3, 5, 7
- X
- 23
- Betrag
- 105
- Produkt
- 105
- Anzahl
- 3
Sie übergeben zwei parallele Arrays; die Engine prüft die Teilerfremdheit, faltet die Kongruenzen mit sukzessivem CRT unter Verwendung exakter ganzzahliger gcds und modularer Inverser und meldet den kanonischen Vertreter im Bereich von null bis Produkt minus eins. Die Berechnung ist reine Integer-Arithmetik: kein Netzwerk, kein Zufall und keine Uhr, sodass dieselben Arrays stets dasselbe x ergeben.
Was der chinesische Restsatz besagt
Der Satz beantwortet ein altes Rätsel: Welche Zahl lässt beim Teilen durch 3 den Rest 2, beim Teilen durch 5 den Rest 3 und beim Teilen durch 7 den Rest 2? Sind die Teiler, die Moduln, paarweise teilerfremd, haben also keine zwei einen gemeinsamen Faktor größer als eins, dann gibt es genau eine Antwort zwischen null und ihrem Produkt minus eins. Hier ist das Produkt 105 und die Antwort 23. Jede andere passende Zahl ist 23 plus oder minus ein Vielfaches von 105, ein Ergebnis beschreibt also eine ganze Familie von Lösungen.
Wie gerechnet wird und was oft schiefgeht
Der Rechner beginnt mit der ersten Kongruenz und nimmt die übrigen nacheinander hinzu. In jedem Schritt bestimmt er mit dem erweiterten euklidischen Algorithmus ein modulares Inverses und passt die Teillösung so an, dass sie eine Bedingung mehr erfüllt. Gerechnet wird nur mit ganzen Zahlen, gerundet wird also nichts. Der häufigste Fehler sind Moduln mit gemeinsamem Faktor, etwa 4 und 6: Ein solches System hat womöglich keine oder mehrere Lösungen und wird deshalb abgelehnt statt geraten. Vergessen Sie außerdem nicht, dass die Antwort für eine ganze Klasse von Zahlen steht.
Wie sukzessives CRT die Lösung exakt berechnet und wo es eingesetzt wird
Intern beginnt die Engine mit der ersten Kongruenz und führt wiederholt die nächste hinzu. Gegeben eine Teillösung x kongruent x0 modulo m und eine neue Kongruenz x kongruent a modulo n mit m und n teilerfremd, berechnet sie das modulare Inverse von m modulo n mit dem erweiterten euklidischen Algorithmus, multipliziert es mit der reduzierten Differenz a minus x0 und hebt x0 um m mal diesen Schritt an, um die neue Teillösung modulo m mal n zu erhalten.
Studierende begegnen dieser Konstruktion, wenn Lehrbücher verlangen, eine Zahl aus ihren Resten zu rekonstruieren; Lehrende können Lösungsschlüssel für Arbeitsblätter mit simultanen Kongruenzen erzeugen, ohne undurchsichtigen Rechnern vertrauen zu müssen; Entwickler nutzen denselben Vertrag, um modulare Rekonstruktionen in didaktischen RSA-Demos zu validieren, wo CRT mit teilerfremden Primfaktoren die Entschlüsselung beschleunigt, und um deterministische Testvektoren für Bibliotheken der modularen Arithmetik zu bauen.
Anwendungsfälle
Hausaufgaben und Wettbewerbs-Kongruenzsysteme
Lösen Sie Lehrbuchsysteme wie x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 und erhalten Sie die kleinste nichtnegative Lösung samt Produkt der Moduln.
Didaktische RSA- und Rekonstruktions-Demos
Führen Sie Reste modulo teilerfremder Faktoren zu einer einzigen Ganzzahl zusammen, wenn Sie CRT-basierte RSA-Beschleunigungen, Kalenderrätsel oder Ringisomorphismen erklären.
Häufige Fragen
Was kostet der Chinesischer-Restsatz-Rechner?
Im Browser auf dieser Seite ist er kostenlos.
Müssen die Moduln paarweise teilerfremd sein?
Ja. Dieser Rechner verlangt paarweise teilerfremde Moduln, was eine eindeutige Lösung modulo ihres Produkts garantiert.
Ist der Algorithmus zufallsbasiert?
Nein. Er verwendet deterministisches sukzessives CRT mit exaktem ganzzahligem gcd und modularen Inversen. Dieselben Reste und Moduln ergeben stets dieselbe kleinste nichtnegative Lösung.
Dürfen die Reste negativ sein?
Ja. Jeder negative Rest wird zuerst modulo seinem eigenen Modul reduziert und dann wie der gleichwertige Wert zwischen null und Modul minus eins behandelt. Danach wird das System ganz normal gelöst.
Warum gibt es unterhalb des Produkts der Moduln nur eine Antwort?
Weil der Satz bei paarweise teilerfremden Moduln genau eine Lösungsklasse modulo diesem Produkt garantiert. Im klassischen Beispiel unterscheidet sich jede andere Lösung von 23 um ein Vielfaches von 105, also ist 23 die kleinste.
Verwandte Tools
Für Entwickler — API-Zugang
Alles auf dieser Seite ist auch per API verfügbar. Dieser Abschnitt richtet sich an Teams, die es in ihre eigenen Systeme einbinden möchten; alle anderen nutzen einfach das Tool oben.
Endpunkt
Authentifizierung per Bearer-Token. Ein einziger POST stellt die Aufgabe in die Warteschlange; das Ergebnis erhalten Sie per Webhook oder über einen signierten Link.
Aufruf aus Ihrem Stack
curl -X POST https://api.kit.forhosting.com/math/chinese-remainder \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"remainders":[2,3,2],"moduli":[3,5,7]}'const res = await fetch("https://api.kit.forhosting.com/math/chinese-remainder", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/chinese-remainder",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/chinese-remainder", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"remainders":[2,3,2],"moduli":[3,5,7]}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"remainders":[2,3,2],"moduli":[3,5,7]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/chinese-remainder", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Beispiel-Anfrage
{
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.chinese_remainder",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}Die API arbeitet asynchron: Sie erhalten sofort eine task_id. Polling ist mit 1 Anfrage pro Sekunde erlaubt.
Preis
Der Preis steht auf der Seite – keine Tokens, keine Credits. Fehlgeschlagene Aufgaben werden nicht berechnet.
Limits
max_items | 64 |
Fehler
| HTTP | Code | Bedeutung |
|---|---|---|
401 | unauthorized | Der API-Schlüssel fehlt oder ist ungültig – prüfen Sie den Authorization-Header (Bearer). |
402 | insufficient_balance | Ihr Guthaben reicht für diese Aufgabe nicht aus – Aufladungen verfallen nicht. |
404 | unknown_type | Unbekannter Aufgabentyp – prüfen Sie das Feld „type“ gegen den Katalog. |
429 | rate_limited | Zu viele Anfragen – warten Sie kurz; Polling ist mit 1 Anfrage pro Sekunde erlaubt. |
Technische Hinweise
Der Chinesischer-Restsatz-Rechner löst ein System simultaner Kongruenzen — x kongruent zu jedem Rest a_i modulo jedes Moduls n_i — sofern die Moduln paarweise teilerfremd sind, und gibt die kleinste nichtnegative Lösung zusammen mit dem Produkt der Moduln zurück. Teilt ein Modulpaar einen gemeinsamen Faktor, schlägt die Anfrage mit einem klaren invalid_input-Fehler fehl, statt eine Antwort zu raten.
Was der chinesische Restsatz für teilerfremde Moduln garantiert
Systeme, deren Moduln nicht paarweise teilerfremd sind, werden abgelehnt statt gelöst — das hält den Vertrag einfach und ehrlich. Der klassische chinesische Restsatz besagt: Wenn die Moduln n_1 bis n_k paarweise teilerfremd sind — also jedes Paar keinen gemeinsamen Faktor größer als eins teilt —, dann existiert genau eine Restklasse modulo des Produkts aller n_i, die jede Kongruenz x kongruent a_i modulo n_i gleichzeitig erfüllt. Das berühmte Schulbeispiel, x kongruent 2 modulo 3, x kongruent 3 modulo 5 und x kongruent 2 modulo 7, liefert x gleich 23 modulo 105, und 23 ist die kleinste nichtnegative Lösung, die dieses Werkzeug zurückgibt. Im Erfolgsfall enthält die JSON-Antwort x, den Modulus (der hier dem Produkt der Eingabemoduln entspricht), das Produkt selbst, die auf das kanonische Intervall von null bis n_i minus eins reduzierten Reste, eine Kopie der Moduln und die Anzahl der Kongruenzen.
Wie Eingaben validiert werden und warum nicht teilerfremde Moduln abgelehnt werden
Die akzeptierten Felder sind remainders und moduli, zwei gleich lange JSON-Arrays ganzer Zahlen, wobei die Aliase a, ai und residues auf remainders sowie n, ni und mods auf moduli abgebildet werden, sodass Formulare, Query-Strings und ältere Notebooks denselben Vertrag teilen. Jeder Eintrag darf eine JSON-Ganzzahl oder eine Dezimalzeichenkette mit optionalem führenden Vorzeichen sein; Brüche, wissenschaftliche Notation und eingebettete Leerzeichen werden abgelehnt. Jeder Modulus muss eine positive sichere Ganzzahl sein, Reste dürfen negativ sein und werden vor dem Zusammenführen auf das kanonische Intervall reduziert, und höchstens vierundsechzig Kongruenzen werden pro Anfrage akzeptiert. Vor jeder Berechnung prüft die Engine jedes Modulpaar mit dem euklidischen gcd-Algorithmus; hat ein Paar einen gcd größer als eins, schlägt die Anfrage mit invalid_input fehl, und eine Meldung nennt das betroffene Paar, etwa dass der gcd von 4 und 6 gleich 2 ist. Das ist eine bewusste Designentscheidung, keine Grenze der Mathematik: Allgemeine CRT-Systeme mit gemeinsamen Faktoren können inkonsistent sein, und statt stillschweigend die Semantik zu wechseln, hält dieser Rechner ein einziges Versprechen — paarweise teilerfremd hinein, kleinste nichtnegative Lösung heraus. Fehlende Arrays, ungleiche Längen, nicht ganzzahlige Einträge und Produkte, die den sicheren Ganzzahlbereich überlaufen, scheitern ebenfalls mit invalid_input, sodass eine fehlerhafte Tabellenzelle nie zur stillen falschen Antwort wird.
Wie sukzessives CRT die Lösung exakt berechnet und wo es eingesetzt wird
Auf dieser Seite läuft die Berechnung vollständig und kostenlos in Ihrem Browser; über die API kostet jede erfolgreiche Lösung $0.002, fehlgeschlagene Validierung wird nicht berechnet, und nach der Antwort wird nichts gespeichert.
Integrationsbeispiele
Deterministische Test-Fixtures für Modulo-Bibliotheken
Erzeugen Sie reproduzierbare CRT-Lösungen für Unit-Tests und CI-Assertions, ohne handberechnete Tabellen einzubetten, die von der Implementierung abweichen.
Technische Fragen
Was passiert, wenn die Moduln nicht teilerfremd sind?
Die Anfrage schlägt mit invalid_input fehl, mit einer Meldung wie 'Moduli are not pairwise coprime: gcd(4, 6) = 2', statt unter anderer Semantik eine Antwort zu raten.
Sind negative Reste erlaubt?
Ja. Reste dürfen negativ sein; sie werden vor dem CRT-Zusammenführen auf den Bereich von null bis n_i minus eins reduziert. Moduln müssen positive ganze Zahlen sein.