Der euklidische Algorithmus findet den größten gemeinsamen Teiler (ggT) zweier Zahlen durch wiederholte Division, ganz ohne Primfaktorzerlegung. Für 462/1071 genügen drei Divisionen: Der ggT ist 21, und der Bruch wird zu 22/51. Wenn du nur das Ergebnis brauchst, liefert es der Rechner für den größten gemeinsamen Teiler sofort; dieser Ratgeber erklärt das Verfahren von Hand und warum es immer beim ggT endet.
Die Idee passt in einen Satz: Der ggT zweier Zahlen ändert sich nicht, wenn du die größere durch den Rest ersetzt, den sie bei der Division durch die kleinere lässt. Du wiederholst das, bis der Rest 0 ist, und der letzte Divisor ist der ggT.
Jede Zeile erfüllt Dividend = Quotient × Divisor + Rest, wobei der Rest kleiner als der Divisor ist. In die nächste Zeile wandern nur Divisor und Rest, nicht der Quotient. Das Über-Kreuz-Multiplizieren der Probe ist dasselbe, das beim Vergleichen von Brüchen hilft, und beide Terme durch dieselbe Zahl zu teilen unterscheidet das Kürzen vom Erweitern, wie bei den gleichwertigen Brüchen erklärt.
Warum der Rest genügt
Ist a = q × b + r, dann teilt jede Zahl, die a und b teilt, auch r, denn r = a − q × b. Und umgekehrt: Was b und r teilt, teilt auch a. Die Paare (a, b) und (b, r) haben also dieselben gemeinsamen Teiler, und der größte davon ist derselbe. Deshalb gilt ggT(a, b) = ggT(b, r). Da jeder Rest kleiner ist als der vorige, sinkt die Kette, bis sie bei 0 ankommt.
Dieselbe Idee zeigt sich mit Quadraten. Das Rechteck 1071 mal 462 wird mit zwei Quadraten der Seite 462 belegt; in den verbleibenden Streifen passen drei Quadrate der Seite 147, und in den letzten Streifen sieben der Seite 21. Das kleinste Quadrat, das alles lückenlos füllt, hat die Seite 21, den ggT.
Gerechnetes Beispiel: 462/1071 kürzen
Du willst 462/1071 vollständig kürzen und siehst auf den ersten Blick keinen gemeinsamen Teiler.
- Teile die größere durch die kleinere Zahl. 1071 = 2 × 462 + 147.
- Gehe zum Paar aus Divisor und Rest über. Jetzt sind es 462 und 147: 462 = 3 × 147 + 21.
- Wiederhole mit dem neuen Paar. Es sind 147 und 21: 147 = 7 × 21 + 0. Der Rest ist 0, also endet die Kette.
- Nimm den letzten Divisor. Der ggT ist 21.
- Teile Zähler und Nenner durch 21. 462 ÷ 21 = 22 und 1071 ÷ 21 = 51.
Ergebnis: 462/1071 = 22/51.
Probe: Über Kreuz gilt 462 × 51 = 23.562 und 1071 × 22 = 23.562, also sind die Brüche gleichwertig. Außerdem haben 22 = 2 × 11 und 51 = 3 × 17 keinen gemeinsamen Faktor.
Zweites Beispiel mit fünf Divisionen
Bei 3600/4284 beginnst du mit der größeren Zahl, 4284. Die Kette lautet:
- 4284 = 1 × 3600 + 684
- 3600 = 5 × 684 + 180
- 684 = 3 × 180 + 144
- 180 = 1 × 144 + 36
- 144 = 4 × 36 + 0
Der ggT ist 36, und 3600 ÷ 36 = 100 sowie 4284 ÷ 36 = 119, also wird der Bruch zu 100/119. Beginnst du mit der kleineren Zahl, hat die erste Division den Quotienten 0 und vertauscht nur das Paar; das Ergebnis ist dasselbe, mit einem Schritt mehr.
Euklid oder Primfaktoren
Für einen ggT gibt es zwei Wege, und jeder gewinnt auf einem anderen Gebiet.
| Methode | Was du tust | Ergebnis | Wann sie sich lohnt |
|---|---|---|---|
| Euklid | Mit Rest dividieren, bis der Rest 0 ist | 5 Divisionen, ggT 36 | Große Zahlen, oder wenn du nur den ggT brauchst |
| Primfaktoren | Zerlegen und die gemeinsamen Faktoren mit dem kleinsten Exponenten nehmen | 2² × 3² = 36 | Kleine Zahlen, oder wenn du auch das kgV willst |
Mit 4284 = 2² × 3² × 7 × 17 und 3600 = 2⁴ × 3² × 5² verlangt die Zerlegung, alle Primfaktoren zu finden, und ein großer Faktor verlängert die Suche. Euklid sucht sie nie. Brauchst du neben dem ggT auch das kgV, liefert die Primfaktorzerlegung es direkt, und der Ratgeber zum Unterschied zwischen ggT und kgV erklärt, wann du welches verwendest. Die Teilbarkeitsregeln sparen Schritte, wenn der gemeinsame Teiler offensichtlich ist.
Ein Fehler, der wie ein Ergebnis aussieht
Der häufigste Fehler ist, den Quotienten statt des Rests weiterzureichen. Er liefert einen ggT, der vernünftig wirkt.
Ein ähnlicher Fehler ist, bei einem kleinen Rest stehen zu bleiben, statt auf die 0 zu warten: Der ggT ist der letzte Divisor, nicht der erste Rest, der sich bequem anfühlt. Und zum Kürzen musst du beide Terme durch den ggT teilen, nicht nur einen, sonst ändert sich der Wert.
Wann du ihn nutzt und wie es weitergeht
Euklid arbeitet mit jeweils zwei ganzen Zahlen und liefert nur den ggT. Bei kleinen Brüchen wie 6/8 geht es schneller, die 2 auf einen Blick zu erkennen. Zum Üben mit beliebigen Brüchen wendet das Werkzeug zum Brüche kürzen den ggT an und zeigt die vollständig gekürzte Form. Interessieren dich andere Schreibweisen für einen Bruch, nutzt der Ratgeber zu Kettenbrüchen und ägyptischen Brüchen genau diese Divisionen: Die Quotienten der Kette sind die Glieder des Kettenbruchs.