Startseite › Rechner › Rechner für den erweiterten euklidischen Algorithmus

Rechner für den erweiterten euklidischen Algorithmus

Gib zwei ganze Zahlen ein, um ihren größten gemeinsamen Teiler und die Bézout-Koeffizienten x und y mit a·x + b·y = ggT(a, b) zu erhalten. Jede Division, jeder Quotient und jeder Koeffizient wird in einer Tabelle gezeigt, die du von Hand nachvollziehen oder herunterladen kannst.

Zuletzt aktualisiert:

Ganze Zahl, darf negativ oder sehr groß sein

Leer lassen, um die lineare diophantische Gleichung zu überspringen

Gib deine Werte ein, um das Ergebnis zu sehen.
Anzeige
Anzeige

Anleitung: Rechner für den erweiterten euklidischen Algorithmus

  1. Gib a und b ein, die beiden ganzen Zahlen, mit denen du rechnen willst. Kommas und Leerzeichen in langen Zahlen werden ignoriert.
  2. Gib optional c ein, um die Gleichung a·x + b·y = c in ganzen Zahlen zu lösen.
  3. Klicke auf Berechnen (die Ergebnisse aktualisieren sich auch beim Tippen), um ggT, x, y und die Probe a·x + b·y = ggT zu sehen.
  4. Folge der Tabelle: Jede Zeile zeigt Quotient, Rest und die laufenden Koeffizienten s und t.
  5. Kopiere oder lade herunter: die Antwort oder die Schritt-Tabelle als CSV-Datei für Hausaufgaben oder Notizen.

So funktioniert der erweiterte euklidische Algorithmus

Der euklidische Algorithmus beruht auf einer Tatsache: ggT(a, b) = ggT(b, a mod b). Du teilst die größere Zahl durch die kleinere, behältst den Rest und wiederholst das mit Divisor und Rest, bis der Rest 0 ist. Der letzte Rest ungleich null ist der ggT.

Die erweiterte Version schreibt außerdem jeden Rest als Kombination der ursprünglichen Zahlen, ri = si·a + ti·b. Sie beginnt mit zwei Zeilen, r0 = a (s = 1, t = 0) und r1 = b (s = 0, t = 1), und wendet dann dieselbe Aktualisierung auf alle drei Spalten an:

  • qi = ⌊ri−1 ÷ ri⌋
  • ri+1 = ri−1 − qi·ri,   si+1 = si−1 − qi·si,   ti+1 = ti−1 − qi·ti

Wenn der Rest 0 erreicht, enthält die Zeile darüber den ggT zusammen mit seinen Koeffizienten x = s und y = t.

Rechenbeispiel: ggT(240, 46)

iDivisionqrst
0Start24010
1Start54601
2240 = 5·46 + 104101−5
346 = 4·10 + 616−421
410 = 1·6 + 4145−26
56 = 1·4 + 222−947
64 = 2·2 + 0023−120

Der letzte Rest ungleich null ist 2, also ggT(240, 46) = 2 mit x = −9 und y = 47. Probe: 240 × (−9) + 46 × 47 = −2,160 + 2,162 = 2. Die letzte Zeile (23, −120) ist ein nützliches Nebenprodukt: 240 × 23 − 46 × 120 = 0, und 23 = 46/2 sowie 120 = 240/2 sind die Schritte der allgemeinen Lösung.

Wo er verwendet wird

  • Modulare Inverse. Wenn ggT(a, m) = 1, dann gilt a·x ≡ 1 (mod m). So wird der private Exponent bei der RSA-Schlüsselerzeugung berechnet.
  • Lineare diophantische Gleichungen. a·x + b·y = c hat nur dann ganzzahlige Lösungen, wenn ggT(a, b) die Zahl c teilt; die Koeffizienten liefern direkt eine Lösung.
  • Chinesischer Restsatz. Um Kongruenzen wie x ≡ 2 (mod 3) und x ≡ 3 (mod 5) zu kombinieren, braucht man Inverse des einen Moduls modulo des anderen.
  • Brüche und Verhältnisse. Die Division durch den ggT kürzt einen Bruch vollständig.

Tipp: Die Koeffizienten, die diese Methode liefert, sind die „minimalen“, in den meisten Fällen mit |x| ≤ b/(2g) und |y| ≤ a/(2g), sodass sie selten größer als die Eingaben werden.

Häufige Fragen

Was macht der erweiterte euklidische Algorithmus?

Er bestimmt den größten gemeinsamen Teiler zweier ganzer Zahlen a und b und gleichzeitig zwei ganze Zahlen x und y, sodass a·x + b·y = ggT(a, b). Der gewöhnliche euklidische Algorithmus liefert nur den ggT; die erweiterte Version verfolgt, wie jeder Rest aus a und b zusammengesetzt ist.

Was sind Bézout-Koeffizienten?

Das sind die ganzen Zahlen x und y im Lemma von Bézout a·x + b·y = ggT(a, b). Sie existieren immer, wenn a und b nicht beide null sind, sind aber nicht eindeutig: Wenn (x, y) passt, dann auch (x + k·b/g, y − k·a/g) für jede ganze Zahl k, wobei g der ggT ist.

Wie bestimme ich mit diesem Rechner ein modulares Inverses?

Gib die Zahl als a und den Modul als b ein. Wenn ggT(a, b) = 1, erfüllt der Koeffizient x die Bedingung a·x ≡ 1 (mod b), also ist x modulo b reduziert das Inverse. Zum Beispiel ist das Inverse von 17 modulo 3120 gleich 2753, denn 17 × 2753 = 46,801 = 15 × 3120 + 1. Ist der ggT größer als 1, existiert kein Inverses.

Warum ist einer meiner Koeffizienten negativ?

Bei positivem a und b ist fast immer einer der Werte x und y negativ (oder null), weil a·x + b·y so klein wie der ggT werden muss. Das ist zu erwarten. Wenn du b/g zu x addierst und a/g von y abziehst, erhältst du ein weiteres gültiges Paar, falls du ein positives x bevorzugst.

Wann hat a·x + b·y = c ganzzahlige Lösungen?

Genau dann, wenn ggT(a, b) die Zahl c teilt. Dann multiplizierst du die Bézout-Koeffizienten mit c / ggT(a, b), um eine Lösung zu erhalten, und die allgemeine Lösung addiert Vielfache von b/g zu x und subtrahiert dieselben Vielfachen von a/g von y. Teilt der ggT c nicht, gibt es keine ganzzahligen Lösungen.

Wie viele Schritte braucht der euklidische Algorithmus?

Sehr wenige. Nach dem Satz von Lamé ist die Anzahl der Divisionsschritte höchstens etwa fünfmal so groß wie die Stellenzahl der kleineren Zahl. Der ungünstigste Fall sind zwei aufeinanderfolgende Fibonacci-Zahlen wie 89 und 55, bei denen jeder Quotient 1 ist.

Kann ich negative oder riesige Zahlen verwenden?

Ja. Der Rechner arbeitet mit exakter Ganzzahlarithmetik beliebiger Länge bis zu 400 Stellen. Bei negativen Eingaben führt er den Algorithmus mit den Beträgen aus und dreht dann das Vorzeichen des zugehörigen Koeffizienten um, sodass a·x + b·y = ggT weiterhin gilt. Der ggT selbst wird immer als nicht negative Zahl angegeben.

Werden alle Tools auf FreeToolCabin auf Qualität und Genauigkeit getestet?

Ja. Jedes Tool auf der Website durchläuft automatische Tests in echten Browsern, die prüfen, ob das Ergebnis stimmt und keine Fehler auftreten. Wenn du einen Fehler findest oder einen Vorschlag hast, schreib uns an [email protected] – wir sehen es uns an.

Ähnliche Tools

Alle Algebra- & Analysisrechner ansehen →