Zum Inhalt springen
OneKitly

Euklids Algorithmus liefert den ggT und das Rezept, ihn zu bauen

Veröffentlicht am 27.10.2026 · 3 Min. Lesezeit · Alltags-Rechner

Daniel Okonkwo

Daniel Okonkwo — Front-end-Entwickler und Tech-Redakteur bei OneKitly

Web-Performance · Dateiformate

Anhand von 2 Quellen geprüft

Profil ansehen →
Kurz gesagt

Der gewöhnliche Algorithmus ersetzt die größere Zahl immer wieder durch ihren Rest gegen die kleinere: 252 lässt gegen 105 den Rest 42, 105 gegen 42 den Rest 21, und 42 gegen 21 nichts — der größte gemeinsame Teiler ist also 21. Die erweiterte Fassung merkt sich unterwegs, wie jeder Rest entstand, und liefert zwei ganze Zahlen, die die Ausgangszahlen zu diesem Teiler kombinieren — hier −2 und 5, denn 252 × (−2) + 105 × 5 = −504 + 525 = 21. Diese Kombination existiert immer, ein Sachverhalt namens Bézout-Identität, und sie erzeugt das modulare Inverse: Ist der Teiler eins, so ist der Koeffizient der ersten Zahl genau deren Inverses modulo der zweiten.

Werbung

252 und 105 haben den größten gemeinsamen Teiler 21, und die erweiterte Fassung liefert zusätzlich −2 und 5: 252 × (−2) + 105 × 5 = 21 genau.

Warum er so schnell endet

Jeder Schritt ersetzt ein Paar durch ein kleineres, und das Schrumpfen geht schnell: Nach zwei Schritten ist die größere Zahl höchstens halb so groß wie zuvor, denn ein Rest ist stets kleiner als der Divisor und eines von beiden muss unter die Hälfte fallen. Die Schrittzahl ist daher der Stellenzahl proportional und nicht den Zahlen selbst — deshalb bewältigt das Verfahren Werte mit Hunderten von Stellen mühelos. Der schlechteste Fall sind ausgerechnet aufeinanderfolgende Fibonacci-Zahlen, ein hübsches Detail und der Grund, warum die Schranke üblicherweise logarithmisch angegeben wird.

Die Koeffizienten sind nicht eindeutig

Für 240 und 46 liefert der Algorithmus −9 und 47, also 240 × (−9) + 46 × 47 = 2 — eine Antwort unter unendlich vielen: dreiundzwanzig zum ersten Koeffizienten zu addieren und hundertzwanzig vom zweiten abzuziehen ergibt ein weiteres gültiges Paar, und so fort. Der Algorithmus liefert das Paar mit den kleinsten Beträgen, den brauchbaren Vertreter, und jede Implementierung, die zwei Ergebnisse vergleicht, muss normalisieren, bevor sie sie für verschieden erklärt. Das ist eine allgemeine Falle bei Problemen, deren Antworten eine Familie statt eines Punktes bilden.

Die Divisionsschritte für 252 und 105
SchrittRest
252 = 2 × 105 + 4242
105 = 2 × 42 + 2121
42 = 2 × 21 + 00 — Ende
Erweiterter-euklidischer-Algorithmus-RechnerFühre den erweiterten euklidischen Algorithmus für zwei ganze Zahlen a und b aus: er liefert ihren größten gemeinsamen Teiler samt den Bézout-Koeffizienten x und y mit a·x + b·y = ggT(a, b). Über den ggT hinaus sind diese Koeffizienten genau das, was man für modulare Inverse und lineare diophantische Gleichungen braucht. Die vollständige Divisionstabelle zeigt jede Reduktion.Tool ausprobieren →
Werbung

Häufige Fragen

Wie alt ist dieses Verfahren?
Es steht in Euklids Elementen, geschrieben rund dreihundert Jahre vor unserer Zeitrechnung, und ist damit der älteste noch routinemäßig verwendete Algorithmus. Im entscheidenden Sinn wurde daran nichts verbessert: Es gibt Varianten, die ohne Division auskommen oder besser zu Binärhardware passen, aber Schrittzahl und Grundidee sind unverändert. Dass ein für die Geometrie auf Papyrus geschriebenes Verfahren in jedem Gerät steckt, das Public-Key-Kryptographie betreibt, ist eine der auffälligsten Kontinuitäten des Fachs.
Wozu dienen die Koeffizienten außer für Inverse?
Zum Lösen von Gleichungen in ganzen Zahlen — dafür wollte man sie zuerst. Eine Gleichung, die ganzzahlige Mengen zweier Größen verlangt, die zusammen eine dritte ergeben sollen, hat genau dann eine Lösung, wenn der größte gemeinsame Teiler der beiden die dritte teilt, und die Koeffizienten liefern eine davon direkt; die übrigen folgen durch Addition von Vielfachen eines festen Schritts. Das deckt das Zusammenstellen eines Betrags aus zwei Münzwerten ab, das Zusammenfallen zweier wiederkehrender Takte und jede ähnliche Frage, in der Bruchantworten verboten sind. Es ist auch die Maschinerie hinter dem Rekonstruieren eines Werts aus mehreren Resten zugleich.

Artikel, die dich interessieren könnten

Alle Ratgeber →

Ähnliche Tools

Quellen

Hast du einen Fehler in diesem Artikel entdeckt?