Euklidischer Algorithmus
Für 1071 und 462 ist der ggT 21, erreicht in drei Divisionen: 1071 = 462 × 2 + 147, dann 462 = 147 × 3 + 21, dann Rest null. Geben Sie zwei ganze Zahlen ein und sehen Sie jeden Schritt, nicht nur das Ergebnis. 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
- A
- 1.071
- B
- 462
- Gcd
- 21
- Anzahl der Schritte
- 3
Der Rechner für den euklidischen Algorithmus nimmt zwei Ganzzahlen und berechnet ihren größten gemeinsamen Teiler so, wie Euklid es vor über zweitausend Jahren beschrieben hat: durch wiederholtes Dividieren und Weiterrechnen mit dem Rest. Statt nur die Endzahl zurückzugeben, liefert er die vollständige Schrittliste — jede Zeile in der Form Dividend = Divisor × Quotient + Rest —, damit Sie genau sehen, wie das Ergebnis zustande kam. Er akzeptiert negative Werte (der ggT verwendet Beträge), weist nicht ganzzahlige Eingaben zurück und lehnt den undefinierten Fall ggT(0,0) ab.
Was der euklidische Algorithmus tatsächlich tut
Der größte gemeinsame Teiler zweier Ganzzahlen ist die größte Zahl, die beide ohne Rest teilt. Der euklidische Algorithmus findet ihn, ohne irgendetwas zu faktorisieren, und genau deshalb bleibt er selbst bei sehr großen Eingaben schnell. Die Idee ist einfach: Wenn eine Zahl sowohl a als auch b teilt, teilt sie auch den Rest der Division von a durch b.
Also ersetzt man das Paar (a, b) durch (b, a mod b) und wiederholt das. Jeder Schritt ist eine schriftliche Division — zum Beispiel 1071 = 462 × 2 + 147 — und man macht weiter, bis der Rest null ist. Der letzte von null verschiedene Rest ist der ggT.
Da der Rest bei jedem Schritt strikt kleiner wird, endet die Schleife garantiert, und sie endet schnell: Die Anzahl der Schritte ist proportional zum Logarithmus der kleineren Eingabe. Dieser Endpunkt führt genau dieses Verfahren aus und liefert Ihnen jede durchgeführte Division, nicht nur das Ergebnis. Das macht ihn ebenso nützlich zum Korrigieren von Hausaufgaben wie zum Nachprüfen einer Berechnung in einem größeren System.
Eingaben, Grenzfälle und wie Fehler gemeldet werden
Sie senden zwei Felder, a und b, und beide müssen Ganzzahlen sein. Negative Ganzzahlen sind gültig: Der ggT ist über Beträge definiert, also ist ggT(-1071, 462) dasselbe wie ggT(1071, 462), und die Schrittliste wird über die Beträge berechnet. Null ist eine gültige Eingabe für eines der Felder — ggT(a, 0) ist |a|, und in diesem Fall ist die Schrittliste leer, weil keine Division nötig ist —, aber zwei Nullen werden abgelehnt, weil ggT(0,0) mathematisch undefiniert ist.
Fehler erzeugen niemals eine Teilantwort: Die Anfrage wird mit einem maschinenlesbaren Code und einer Meldung abgelehnt, die Sie dem Benutzer anzeigen können.
Wo ein ggT mit Schrittliste seinen Wert beweist
Der nackte ggT ist eine Standardware — jede Sprache hat einen in ihrer Standardbibliothek. Was diese Fähigkeit hinzufügt, ist die Nachverfolgung. Lehrkräfte und Studierende nutzen die Schrittliste, um zu prüfen, ob eine Aufgabe wirklich mit dem euklidischen Algorithmus gelöst wurde statt durch Erraten von Teilern.
Entwicklerinnen und Entwickler nutzen sie beim Debuggen von Bruchkürzung, Seitenverhältnisreduktion oder Teilerfremdheitsprüfungen, denn die Zeile 252 = 105 × 2 + 42 zeigt genau, wo eine Handrechnung vom Code abweicht. Wer Kryptografie lernt, begegnet dem Algorithmus als Grundlage der erweiterten Version, die Bézout-Koeffizienten und modulare Inverse liefert; wer zuerst die einfachen Divisionsschritte sieht, dem fällt dieser Sprung deutlich leichter.
Anwendungsfälle
Eine gelöste Aufgabe nachprüfen
Fügen Sie die beiden Zahlen einer Hausaufgabe ein und vergleichen Sie Ihre handschriftlichen Divisionsschritte mit denen, die der Algorithmus tatsächlich erzeugt.
Brüche und Verhältnisse kürzen
Ermitteln Sie den ggT von Zähler und Nenner, um einen Bruch zu kürzen — mit der Schrittliste als Prüfprotokoll, wie der Teiler gefunden wurde.
Den Algorithmus vor der erweiterten Version lehren
Zeigen Sie Lernenden zuerst die einfache Divisionsfolge und gehen Sie dann zu Bézout-Koeffizienten und modularen Inversen über, die auf derselben Schleife aufbauen.
Häufige Fragen
Was kostet das?
Die Ausführung in Ihrem Browser auf dieser Seite ist außerdem kostenlos.
Warum wird ggT(0,0) abgelehnt?
Weil der größte gemeinsame Teiler von null und null undefiniert ist — jede Ganzzahl teilt null, also gibt es keine größte. Geben Sie mindestens einen Wert ungleich null an.
Kann ich negative Zahlen übergeben?
Ja. Der ggT wird über Beträge berechnet, daher liefert ggT(-1071, 462) dasselbe Ergebnis wie ggT(1071, 462).
Was enthält das Array steps?
Ein Objekt pro Division: Dividend, Divisor, Quotient und Rest, sodass jede Zeile als Dividend = Divisor × Quotient + Rest gelesen wird. Der letzte von null verschiedene Rest ist der ggT.
Wie groß dürfen die Eingaben sein?
Bis zur größten sicheren Ganzzahl, 9007199254740991, sodass jeder Quotient und jeder Rest in der Ausgabe exakt ist.
Was passiert, wenn eine der beiden Zahlen null ist?
Dann ist der ggT der Betrag der anderen Zahl, und die Liste der Schritte bleibt leer, weil keine Division nötig ist. Nur wenn beide Zahlen null sind, wird die Eingabe abgelehnt, da dieser Fall nicht definiert ist.
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/euclidean-algorithm \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":1071,"b":462}'const res = await fetch("https://api.kit.forhosting.com/math/euclidean-algorithm", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 1071,
"b": 462
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/euclidean-algorithm",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 1071,
"b": 462
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/euclidean-algorithm", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":1071,"b":462}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":1071,"b":462}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/euclidean-algorithm", 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": 1071,
"b": 462
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.euclidean_algorithm",
"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
Derselbe Code läuft kostenlos in Ihrem Browser auf dieser Seite und über die kostenpflichtige API.
Eingaben, Grenzfälle und wie Fehler gemeldet werden
Numerische Zeichenketten, die exakte Ganzzahlen darstellen, wie "1071", werden akzeptiert; Dezimalzahlen, Brüche, wissenschaftliche Notation und nicht numerische Werte werden mit einem invalid_input-Fehler abgewiesen, der erklärt, was falsch war. Die Werte sind durch den sicheren Ganzzahlbereich von IEEE-754-Doubles begrenzt, etwa 9 Billiarden, sodass jeder Quotient und jeder Rest in der Ausgabe exakt ist.
Technische Fragen
Was gilt als Ganzzahl?
Eine JSON-Zahl ohne Nachkommastellen oder eine Zeichenkette aus Ziffern mit optionalem Vorzeichen. Dezimalzahlen, wissenschaftliche Notation und nicht numerische Werte werden mit einem invalid_input-Fehler abgewiesen.