Erweiterter Euklid: ggT und Bézout-Koeffizienten x, y
Für 240 und 46 ist der größte gemeinsame Teiler 2, und 240 × (−9) + 46 × 47 = 2. Geben Sie zwei ganze Zahlen ein und erhalten Sie den Teiler, beide Bézout-Koeffizienten und die Gleichung als Beleg. 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
- Erste ganze Zahl
- 240
- Zweite ganze Zahl
- 46
- ggT
- 2
- X
- -9
- Y
- 47
- Prüfung
- 2
Der erweiterte euklidische Algorithmus meldet nicht nur den größten gemeinsamen Teiler zweier ganzer Zahlen: er liefert auch Bézout-Koeffizienten x und y, sodass a mal x plus b mal y diesen ggT ergibt. Diese Koeffizienten erscheinen bei modularen Inversen, wenn der ggT eins ist, in konstruktiven Beweisen linearer diophantischer Gleichungen und in Krypto-Hausaufgaben, die eine explizite Kombination statt eines bloßen Rests brauchen.
Von Resten zu Bézout-Koeffizienten
Gewöhnliche euklidische Division ersetzt wiederholt ein Paar (a, b) durch (b, a mod b), bis der Rest null ist; der letzte nicht-null Rest ist ggT(a, b). Die erweiterte Form verfolgt, wie jeder Rest als ganzzahlige Linearkombination der ursprünglichen Eingaben geschrieben wird. In jedem Schritt gilt der aktuelle Rest gleich a mal ein Koeffizient plus b mal ein anderer, und wenn der Algorithmus stoppt, sind diese Koeffizienten genau die Bézout-Zahlen des ggT.
Unterrichtspräsentationen nutzen oft Rücksubstitution aus der Quotientenfolge; Produktionscode aktualisiert iterativ zwei Koeffizientenpaare, ohne einen Reststapel zu speichern. Beide Wege berechnen dasselbe mathematische Objekt: ganze Zahlen x und y mit a*x + b*y = ggT(a, b). Dieser Endpunkt implementiert den iterativen Pfad auf Absolutwerten und multipliziert Vorzeichen zurück, damit negative Eingaben die Identität noch erfüllen.
Der ggT selbst wird stets als nichtnegative ganze Zahl zurückgegeben, passend zur Standardkonvention in Bibliotheken und Wettbewerbsaufgaben.
Wo Bézout-Koeffizienten in der Praxis auftauchen
Wettbewerbsprogrammierer lösen ax + by = c, indem sie zuerst ggT und Basiskoeffizienten berechnen, dann skalieren und die allgemeine Lösung parametrisieren, wenn der ggT c teilt. Krypto-Studierende holen modulare Inverse für RSA-Spielbeispiele und affine Chiffren, wenn ggT(a, m) eins ist, indem sie den Koeffizienten von a nach Reduktion modulo m lesen. Lehrkräfte vergeben konstruktive Beweise, dass zwei ganze Zahlen teilerfremd sind, und brauchen ein deterministisches Orakel, das die Kombination zeigt, nicht nur ein Wahr-Falsch-Bit.
Daten- und Systemingenieure brauchen gelegentlich explizite Linearkombinationen beim Abstimmen periodischer Pläne oder Schritt-Arithmetik. Nutzen Sie das Browser-Werkzeug zum schnellen Hausaufgaben-Check und automatisieren Sie denselben Vertrag, wenn Ihr Dienst Massen-Diophant-Prüfungen braucht. Wenn Sie nur den reinen ggT ohne Koeffizienten brauchen, beantwortet diese Seite jenen Bedarf und lehrt zugleich das stärkere konstruktive Ergebnis.
Anwendungsfälle
Lineare diophantische Gleichungen
Holen Sie eine partikuläre Lösung (x, y) für a*x + b*y = ggT, skalieren und parametrisieren Sie dann beim Lösen von a*x + b*y = c in Wettbewerben oder Hausaufgaben.
Baustein des modularen Inversen
Wenn ggT(a, m) = 1, reduzieren Sie den Bézout-Koeffizienten von a modulo m, um ein modulares Inverses für Krypto- und Zahlentheorie-Übungen zu erhalten.
Häufige Fragen
Was ist der erweiterte euklidische Algorithmus?
Er berechnet ggT(a, b) und ganze Zahlen x, y (Bézout-Koeffizienten), sodass a*x + b*y diesem ggT gleicht, indem er Linearkombinationen durch die euklidischen Restschritte verfolgt.
Sind die Koeffizienten eindeutig?
Nein. Wenn (x, y) funktioniert, gilt auch (x + k*(b/g), y − k*(a/g)) für jedes ganze k. Dieses Werkzeug liefert eine partikuläre Lösung des iterativen Algorithmus.
Welcher Ganzzahlbereich wird unterstützt?
Jedes von a und b muss eine ganze Zahl mit Absolutwert höchstens 9007199254740991 (Number.MAX_SAFE_INTEGER) sein.
Wie finde ich die Bézout-Koeffizienten von 240 und 46?
Geben Sie beide Zahlen ein. Der größte gemeinsame Teiler ist 2, die Koeffizienten sind −9 und 47, denn 240 × (−9) + 46 × 47 = 2. Das Ergebnis enthält diese Gleichung zum Nachprüfen.
Wie erhalte ich daraus ein modulares Inverses?
Ist der größte gemeinsame Teiler 1, dann ist der Koeffizient der ersten Zahl, reduziert modulo der zweiten, das Inverse der ersten Zahl modulo der zweiten. So geht man bei RSA-Beispielen und affinen Chiffren vor.
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/numth/extended-euclidean \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":240,"b":46}'const res = await fetch("https://api.kit.forhosting.com/numth/extended-euclidean", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 240,
"b": 46
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/extended-euclidean",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 240,
"b": 46
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/extended-euclidean", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":240,"b":46}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":240,"b":46}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/extended-euclidean", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Beispiel-Anfrage
{
"a": 240,
"b": 46
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.extended_euclidean",
"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_abs | 9007199254740991 |
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
Diese Fähigkeit nimmt zwei ganze Zahlen, lehnt den undefinierten Fall ab, in dem beide null sind, und gibt ein stabiles JSON mit ggT, x, y, einer Verifikation und einer lesbaren Gleichung zurück, die Sie in Notizen oder Tests einfügen können.
Was Sie senden und was Sie zurückerhalten
Bei Erfolg enthält die Antwort normalisierte a und b, ggT, x, y, ein verschachteltes bezout-Objekt mit denselben Koeffizienten, eine numerische Prüfung gleich a*x + b*y und eine Gleichungszeichenkette wie 240*(-9) + 46*(47) = 2. Typische Checks: für 240 und 46 ist der ggT 2 und eine gültige Lösung ist x gleich minus neun mit y gleich siebenundvierzig; für ein Primpaar mit ggT eins liefern die Koeffizienten nach Reduktion von x ein modulares Inverses von a modulo b. Randfälle mit einer Null und einem nicht-null Partner ergeben ggT gleich dem Absolutwert der nicht-null Eingabe und ein triviales Koeffizientenmuster. Geben Sie ganze Zahlen a und b an (Aliase first oder m für a sowie second oder n für b werden akzeptiert). Nicht-Ganzzahlen, leere Felder und Werte außerhalb des plattformweiten sicheren Ganzzahl-Absolutmaximums werden mit invalid_input abgelehnt und nicht berechnet. Das Paar null und null wird ebenfalls abgelehnt, weil ggT(0, 0) undefiniert ist und keine Koeffizienten eine sinnvolle Gleichung ergeben.
Wo Bézout-Koeffizienten in der Praxis auftauchen
Weil die Fähigkeit eine reine Parse-Engine ist, gibt es keinen Modelldrift, keine Netzwerkabhängigkeit und keinen gespeicherten Zustand: dasselbe Paar liefert bei fester Koeffizientenkonvention immer dasselbe JSON. Der API-Preis ist die veröffentlichte Basis von $0.002 pro erfolgreichem Element; fehlgeschlagene Validierung wird nicht berechnet.
Integrationsbeispiele
Lehre und automatisierte Prüfungen
Zeigen Sie Studierenden die Identität a*x + b*y = ggT mit einem stabilen JSON-Gleichungsfeld und verdrahten Sie denselben Vertrag in Bewerter oder CI-Fixtures.
Technische Fragen
Warum werden a und b beide null abgelehnt?
ggT(0, 0) ist undefiniert. Es gibt keinen positiven größten gemeinsamen Teiler, daher gibt die API invalid_input zurück und berechnet nicht.
Was kostet es?
Das Browser-Werkzeug ist kostenlos und läuft lokal. API-Anfragen nutzen vorausbezahltes KIT-Guthaben zu $0.002 pro erfolgreichem Element; ungültige Eingabe wird nicht berechnet.