Erweiterten euklidischen Algorithmus berechnen
Berechne ggT und Bézout-Koeffizienten mit dem erweiterten euklidischen Algorithmus. Prüfe die Identität und jeden Rest- und Quotientenschritt.
Beispiele für den erweiterten euklidischen Algorithmus
Der Algorithmus findet Koeffizienten x und y mit a × x + b × y = ggT(a, b).
| Eingaben | ggT | Bézout-Identität |
|---|---|---|
| 240 und 46 | 2 | −9 × 240 + 47 × 46 = 2 |
| 56 und 15 | 1 | −4 × 56 + 15 × 15 = 1 |
| 99 und 78 | 3 | −11 × 99 + 14 × 78 = 3 |
| 35 und 15 | 5 | 1 × 35 + (−2) × 15 = 5 |
| 101 und 23 | 1 | −5 × 101 + 22 × 23 = 1 |
Häufige Fragen
Was berechnet der erweiterte euklidische Algorithmus?
Er berechnet den größten gemeinsamen Teiler zweier ganzer Zahlen a und b sowie ganze Zahlen x und y mit der Identität a × x + b × y = ggT(a, b). Der normale euklidische Algorithmus liefert nur den ggT. Die erweiterte Variante verfolgt zusätzlich die Koeffizienten jedes Restes.
Was sind Bézout-Koeffizienten, und warum sind sie wichtig?
Die Bézout-Koeffizienten sind die ganzen Zahlen x und y in der Gleichung a × x + b × y = ggT(a, b). Sie zeigen den ggT als ganzzahlige Linearkombination der Eingaben. Damit lassen sich unter anderem modulare Inversen und lineare diophantische Gleichungen berechnen.
Wie liest du die Tabelle des Algorithmus?
Jede Tabellenzeile enthält einen Rest r und Koeffizienten s und t mit s × a + t × b = r. Die ersten beiden Zeilen beginnen mit a und b. Danach wird jeweils ein ganzzahliges Quotientenvielfaches abgezogen. Der Betrag des letzten Rests ungleich null ist der ggT. Nach der Vorzeichen-Normalisierung liefern seine Koeffizienten x und y.
Sind die Bézout-Koeffizienten eindeutig?
Nein. Aus einem Lösungspaar können unendlich viele weitere Paare gebildet werden, ohne die Bézout-Identität zu verändern. Der Rechner gibt das Paar aus, das durch die konkrete Restfolge des erweiterten Algorithmus entsteht, und zeigt zusätzlich die Prüfung der Identität.
Dürfen a und b null oder negativ sein?
Ja. Wenn genau eine Eingabe null ist, entspricht der ggT dem Betrag der anderen Eingabe. Negative Werte sind ebenfalls zulässig, und der ggT wird immer nicht negativ angegeben. Nur der Fall ggT(0, 0) wird abgelehnt, weil er mathematisch nicht definiert ist.
Änderungsverlauf
Aktualisierungen von Erweiterten euklidischen Algorithmus berechnen, nach Datum gruppiert.
1 Aktualisierung
Erweiterten euklidischen Algorithmus berechnen hinzugefügt
- Berechne ggT und Bézout-Koeffizienten mit dem erweiterten euklidischen Algorithmus. Prüfe die Identität und jeden Rest- und Quotientenschritt.
Ähnliche Rechner
Weitere geprüfte Rechner im Themenbereich „Mathematik“.