Euklids Algorithmus liefert den ggT und das Rezept, ihn zu bauen
Veröffentlicht am 27.10.2026 · 3 Min. Lesezeit · Alltags-Rechner
Daniel Okonkwo — Front-end-Entwickler und Tech-Redakteur bei OneKitly
Web-Performance · Dateiformate
Anhand von 2 Quellen geprüft
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.
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.
| Schritt | Rest |
|---|---|
| 252 = 2 × 105 + 42 | 42 |
| 105 = 2 × 42 + 21 | 21 |
| 42 = 2 × 21 + 0 | 0 — Ende |
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?