Zum Hauptinhalt springen
CalcMax

Euklidischer-Algorithmus-Rechner

Bereich: 1 – 1.000.000

Bereich: 1 – 1.000.000

Ergebnis

21

Größter gemeinsamer Teiler

Schritt für Schritt
1071 = 2 * 462 + 147; 462 = 3 * 147 + 21; 147 = 7 * 21 + 0

Der euklidische Algorithmus findet den größten gemeinsamen Teiler zweier ganzer Zahlen, ohne eine der beiden zu faktorisieren. Er beruht auf einem einzigen Satz: Wenn a = q * b + r gilt, dann teilt jede Zahl, die a und b teilt, auch r, und jede Zahl, die b und r teilt, teilt auch a — die Paare (a, b) und (b, r) haben also genau dieselben gemeinsamen Teiler. Ersetzen Sie das Paar durch das kleinere und wiederholen Sie das Ganze. In jeder Runde werden die Zahlen kleiner, und da sie nicht beliebig kleiner werden können, ist irgendwann eine von ihnen null; die andere ist die Antwort. Für das Paar 1.071 und 462 braucht das Verfahren drei Runden, und keine davon zerlegt eine der beiden Zahlen. Das Panel schreibt sie untereinander: „1071 = 2 * 462 + 147“, „462 = 3 * 147 + 21“, „147 = 7 * 21 + 0“. Der größte gemeinsame Teiler ist damit 21 — drei Runden, zwei Subtraktionen von Vielfachen, nirgends eine Zerlegung in Faktoren. Genau dieser letzte Punkt ist der Grund, das Verfahren zu kennen statt es nur zu benutzen: Um die Teiler einer großen Zahl zu finden, müssten Sie alle Teiler bis zu ihrer Quadratwurzel durchprobieren; der euklidische Algorithmus dagegen teilt immer nur durch eine Zahl, die er schon in der Hand hat, und die Zahlen fallen schnell. Das Paar 610 und 377 — aufeinanderfolgende Fibonacci-Zahlen — ist der schlimmste Fall, den es gibt, und es ist trotzdem nach dreizehn Runden fertig, obwohl beide Zahlen nur drei Stellen haben. Wie viele Runden nötig sind, entscheidet nicht die Größe: 1.000.000 und 999.998 sind viel größer als 610 und 377 und in zwei Runden fertig, weil der zweite Schritt auf einem glatten Vielfachen landet; umgekehrt brauchen 610 und 377 dreizehn. Das Paar mit den meisten Runden für seine Größe ist immer ein Paar aufeinanderfolgender Fibonacci-Zahlen. Dieser Satz hat einen Namen — Satz von Lamé —, und er ist der Grund, warum die Rundenzahl in der Tabelle unten eine eigene Spalte hat. Die beiden Zahlen dürfen in beliebiger Reihenfolge eingegeben werden. Sie vorher absteigend zu sortieren, ist eine Entscheidung dieser Seite und keine Forderung des Verfahrens; deshalb druckt das Paar 462 und 1.071 genau dieselben drei Zeilen wie 1.071 und 462. Die Schritte stehen als Gleichungen da, nicht als schriftliche Division: Jede Runde ist a = q * b + r, und das Semikolon trennt die Runden. Lesen Sie eine Runde als Satz — 1.071 ist 2 mal 462 plus 147 —, dann ist die nächste Runde derselbe Satz mit weitergeschobenen Rollen: 462 ist 3 mal 147 plus 21. Der Rest einer Runde wird der Divisor der nächsten, und der Divisor wird der Dividend.

Drei Paare durch den Algorithmus, mit der Anzahl der Runden

Erste ZahlZweite ZahlRundenggT
1071462321
48180312
3636136

Die beiden rechten Spalten gehören zusammen gelesen, denn sie bewegen sich nicht gemeinsam. Die ersten beiden Zeilen brauchen je drei Runden, die dritte nur eine — schauen Sie aber auf die Antwortspalte: 36 und 36 ergeben 36 in einer einzigen Runde, während 48 und 180 in drei Runden 12 ergeben und 1.071 und 462 in drei Runden 21. Die Größe sagt über keine der beiden Zahlen etwas. Ein größeres Paar ist keine längere Rechnung, und eine längere Rechnung bedeutet keine größere Antwort. Die Rundenspalte zeigt, warum: 36 und 36 fallen sofort zusammen, weil die zweite Zahl die erste glatt teilt, die Schleife endet also im ersten Durchlauf; 48 und 180 dagegen arbeiten sich über 36 und dann 12 herunter, ohne dass einer dieser Schritte glatt aufgeht. Der schlimmste Fall überhaupt ist ein Paar aufeinanderfolgender Fibonacci-Zahlen; deshalb steht als Rechenbeispiel auf dieser Seite 1.071 und 462, das Paar, mit dem der Algorithmus üblicherweise gelehrt wird, und nicht ein größeres Paar, das schneller fertig wäre.

Formel

a = q * b + r, also ggT(a, b) = ggT(b, r); wiederholen, bis r = 0 ist — dann ist b die Antwort

a = q * b + r
Eine Runde des Verfahrens, als Gleichung geschrieben. a ist die größere der beiden Zahlen dieser Runde, b die kleinere, q gibt an, wie oft b ganz in a passt, und r ist der Rest. Genau diese Schreibweise druckt das Panel: 1071 = 2 * 462 + 147 ist eine Runde
a, b
Die beiden Zahlen, die verglichen werden. Sie tauschen in jeder Runde die Rolle: Das b einer Runde wird das a der nächsten, und das r wird das neue b. Wegen dieses Wanderns heißen die Eingabefelder nicht Dividend und Divisor — in der ersten Runde ist 1.071 der Dividend, in der zweiten ist es 462, und eine Beschriftung, die für eine Runde stimmt, stimmt für die anderen nicht
q
Der Quotient, also die Anzahl, wie oft b ganz in a passt. Er ist immer mindestens 1, weil das Paar vor dem Start absteigend sortiert wird — deshalb steht hier nie q = 0. Unauffällig ist nur die letzte Runde, in der der Rest null ist und die Division glatt aufgeht
r
Der Rest, immer kleiner als b und nie negativ. Das Abbruchkriterium ist r = 0, und die Seite druckt es als letzte Runde, statt sie wegzulassen: 147 = 7 * 21 + 0 ist die Zeile, die sagt, dass die Suche zu Ende ist und 21 die Antwort
ggT(a, b)
Größter gemeinsamer Teiler: die größte ganze Zahl, die a und b ohne Rest teilt. Die Antwort ist das b der letzten Runde, direkt aus der Schleife genommen und nicht neu berechnet. Für 1.071 und 462 ist er 21; deshalb gilt 1.071 = 21 × 51 und 462 = 21 × 22, und keine größere Zahl teilt beide
610 = 1 * 377 + 233
Die erste Runde des schlimmsten Falls: aufeinanderfolgende Fibonacci-Zahlen. Hier ist jeder Quotient 1, und die Zahlen schrumpfen kaum — deshalb braucht dieses Paar dreizehn Runden. Der Satz von Lamé besagt, dass kein Paar dieser Größe mehr Runden braucht

Das Kürzen eines Bruchs ist der Alltagsfall. Um 462/1.071 in der Grunddarstellung zu schreiben, brauchen Sie den größten gemeinsamen Teiler der beiden Zahlen, und diese Seite liefert ihn samt Beleg — 21 und die drei Runden, die dorthin geführt haben. Teilen Sie Zähler und Nenner durch 21, bleibt 22/51, und die gedruckten Schritte sind genau das, womit Sie das Kürzen nachprüfen können, statt es zu glauben. Dasselbe Bedürfnis entsteht überall dort, wo ein Verhältnis vereinfacht werden soll: Übersetzungen von Zahnrädern, Seitenverhältnisse von Bildschirmen, Maßstäbe von Zeichnungen und jedes Paar von Messwerten, das Sie lieber als Verhältnis denn als Zahlenpaar hinschreiben. Der zweite Einsatzbereich ist Programmcode und Unterricht: Der Algorithmus ist das erste wirklich interessante Verfahren, das dort gelehrt wird — er bricht ab, er ist schnell, und er ist aus einem einzigen Satz heraus richtig. Außerdem ist er der übliche Weg zu einem modularen Inversen (die erweiterte Fassung führt zwei zusätzliche Zahlen durch dieselben Runden mit), und das ist der Schritt in der Schlüsselerzeugung von RSA. Ein dritter Nutzen ist eine Vorabprüfung beim Faktorisieren: Herauszufinden, dass 1.071 = 3 × 357 und 462 = 2 × 3 × 7 × 11 ist, macht Arbeit; herauszufinden, dass ihr größter gemeinsamer Teiler 21 ist, kostet drei Divisionen. Wer zuerst hier nachsieht, weiß also vorher, ob das Kürzen leicht wird. Wenn Sie nur die Antwort wollen und nicht den Weg, stellt der GGT-Rechner dieselbe Frage in kürzerer Form und verkraftet mehr als zwei Zahlen auf einmal; der KGV-Rechner benutzt den Teiler, um das kleinste gemeinsame Vielfache zu bekommen, denn kgV = (a / ggT) × b; und der Divisionsrest-Rechner erklärt, was ein einzelner Rest bedeutet, wenn die Zahlen negativ sein dürfen — womit diese Seite sich nie befassen muss.

Rechenbeispiele

  1. Das Standardpaar: 1.071 und 462

    1. Wie oft passt 462 in 1.071? Zweimal, und 2 × 462 = 924, es bleiben 1.071 − 924 = 147
    2. Jetzt ist das Paar 462 und 147: 147 passt dreimal in 462, 3 × 147 = 441, es bleiben 21
    3. Jetzt ist das Paar 147 und 21: 21 passt genau siebenmal in 147, es bleibt 0
    4. Der Rest ist null, also endet das Verfahren, und die Antwort ist 21

    Die Standardeingabe und das Rechenbeispiel, mit dem dieser Algorithmus üblicherweise eingeführt wird. Zwei Proben lohnen sich. Teilen Sie beide Zahlen durch 21, erhalten Sie 51 und 22, und diese beiden haben keinen gemeinsamen Teiler mehr — das macht 21 zum größten und nicht bloß zu einem gemeinsamen Teiler. Und beachten Sie, dass hier nirgends faktorisiert wurde: Um die Teiler von 1.071 durch Ausprobieren zu finden, müssten Sie bis 32 rechnen, während der Algorithmus immer nur durch eine Zahl teilt, die er bereits hat. Drei Runden, jede billiger als die vorige.

  2. Eine Runde genügt: 12 und 60

    1. Das Paar wird absteigend sortiert: 60 zuerst, 12 danach
    2. 60 = 5 × 12 + 0, 12 teilt 60 also glatt
    3. Der Rest ist sofort null, deshalb endet der Algorithmus nach einer Runde
    4. Die Antwort ist 12 — die kleinere der beiden Zahlen, weil sie die größere teilt

    Der kürzeste nicht triviale Durchlauf und der Fall, der zeigt, warum die letzte Runde gedruckt wird statt weggelassen. Die Zeile 60 = 5 * 12 + 0 ist die ganze Antwort: Sie sagt, dass der Rest null geworden ist, und das ist die einzige Art, wie dieses Verfahren je endet. Ohne diese Zeile wären die Schritte leer, und niemand könnte unterscheiden, ob eine Runde genügte oder ob die Seite gar nicht gerechnet hat. Immer wenn eine Zahl die andere glatt teilt, ist der größte gemeinsame Teiler einfach die kleinere von beiden.

  3. Teilerfremde Zahlen: 9 und 20

    1. 20 = 2 × 9 + 2, das Paar wird also 9 und 2
    2. 9 = 4 × 2 + 1, das Paar wird 2 und 1
    3. 2 = 2 × 1 + 0, hier endet das Verfahren
    4. Die Antwort ist 1; 9 und 20 haben also keinen gemeinsamen Teiler über 1

    Ein größter gemeinsamer Teiler von 1 ist eine echte Antwort und kein Fehlschlag, und er hat einen Namen: Die Zahlen sind teilerfremd. Er ist zugleich das Zeichen dafür, dass der Bruch 9/20 schon vollständig gekürzt ist, hier also nichts zu vereinfachen bleibt. Beachten Sie, dass die Runden nicht zusammengefallen sind: Das Verfahren ist in drei Schritten bis zur 1 hinuntergelaufen, weil keine der beiden Zahlen die andere glatt geteilt hat. Teilerfremde Paare sind bei wachsenden Zahlen der Normalfall — die Wahrscheinlichkeit, dass zwei zufällig gewählte Zahlen einen gemeinsamen Teiler haben, fällt schnell, und genau das macht das Verfahren beim Bauen eines modularen Inversen in der Kryptografie nützlich.

Einschränkungen

Beide Zahlen müssen ganz sein und zwischen 1 und 1.000.000 liegen. Die Null wird abgelehnt statt als Sonderfall behandelt. Der größte gemeinsame Teiler von a und 0 ist a, eine völlig brauchbare Antwort — nur kann diese Seite sie nicht zeigen: Die erste Runde wäre a = q * 0 + r, und dieses q gibt es nicht. Statt einen Ablauf mit einem Loch zu drucken, lehnt die Seite die Eingabe ab. Negative Zahlen werden aus demselben Grund abgelehnt — die gedruckten Schritte setzen voraus, dass beide Zahlen mindestens 1 sind, und ein negatives Vorzeichen bräuchte eine Regel dafür, was Quotient und Rest bedeuten; diese Regel steht hier nirgends. Die Obergrenze von 1.000.000 hat nichts mit dem Verfahren zu tun, das auch mit weit größeren Zahlen zurechtkäme; sie steht dafür, dass jede Subtraktion, Multiplikation und Division unterwegs in gewöhnlicher Gleitkomma-Arithmetik exakt bleibt und die gedruckte Schrittliste nicht so lang wird, dass sie unlesbar ist. Zwei ziemlich kleine Zahlen können trotzdem viele Runden ergeben — 610 und 377 brauchen dreizehn —, aber die Anzahl ist durch die Obergrenze praktisch begrenzt, und die Tabelle unten hat eine Spalte für die Runden, damit Sie die Schwankung sehen. Die Schritte werden als Gleichungen gedruckt — a = q * b + r, durch Semikolons getrennt — und nicht als schriftliche Division; wer das vertraute Divisionszeichen sucht, bekommt es hier nicht. Die beiden Eingaben sind austauschbar: Die Seite sortiert sie vor dem Start absteigend, deshalb können Sie hier nicht sehen, wie 3 = 0 * 5 + 3 aussähe, weil diese Runde nie entsteht. Wenn Ihre Zahlen negativ sein dürfen oder Sie die Restregel ausgeschrieben haben wollen, ist der Divisionsrest-Rechner die richtige Seite.

Häufige Fragen

Was ist der größte gemeinsame Teiler, in einem Satz?
Die größte ganze Zahl, die beide Zahlen ohne Rest teilt. Für 1.071 und 462 ist das 21: 1.071 = 21 × 51 und 462 = 21 × 22, und 51 und 22 haben keinen gemeinsamen Teiler mehr — das macht 21 zum größten. Beachten Sie, dass 3 und 7 ebenfalls beide Zahlen teilen: Sie sind gemeinsame Teiler, nur nicht die größten. Die Hauptausgabe der Seite ist immer diese Zahl, und die Schritte darunter sind der Beleg.
Warum endet die letzte Zeile immer mit + 0?
Weil ein Rest von null das Einzige ist, was das Verfahren anhält. Die Schleife ersetzt das Paar durch ein kleineres — die zweite Zahl und den Rest —, und die Zahlen fallen in jeder Runde, also müssen sie irgendwann bei null ankommen. 147 = 7 * 21 + 0 ist die Runde, in der das passiert, und der größte gemeinsame Teiler ist der Divisor dieser Runde, also 21. Die Seite druckt sie mit, statt sie zu verstecken: Eine Schrittliste, die beim letzten Rest ungleich null aufhörte, ließe den Leser selbst herausfinden, dass die Suche vorbei ist.
Ist die Reihenfolge der beiden Zahlen wichtig?
Nein. Die Seite sortiert sie vor der ersten Runde absteigend, deshalb liefern 462 und 1.071 genau dieselben drei Zeilen wie 1.071 und 462. Das ist eine Entscheidung und keine Eigenschaft des Verfahrens — wegen ggT(a, b) = ggT(b, a) führt jede Reihenfolge zur richtigen Antwort —, aber ohne diese Sortierung würde die erste Zeile für das Paar 3 und 5 als 3 = 0 * 5 + 3 erscheinen; das ist eine zulässige Division, liest sich aber so, als gehöre es zum Verfahren, eine kleine Zahl durch eine größere zu teilen. Aus demselben Grund heißen die Eingabefelder erste Zahl und zweite Zahl und nicht Dividend und Divisor: Diese beiden Rollen tauschen in jeder Runde.
Was bedeutet eine Antwort von 1?
Dass die beiden Zahlen keinen gemeinsamen Teiler über 1 haben — eine vollständige Antwort und kein Fehlschlag. Solche Zahlen heißen teilerfremd, und das Paar 9 und 20 auf dieser Seite ist ein Beispiel. Sie erfahren damit außerdem etwas Praktisches: Der Bruch 9/20 ist bereits vollständig gekürzt, hier ist nichts zu vereinfachen. Je größer die Zahlen werden, desto häufiger ist der teilerfremde Fall — deshalb ist das Verfahren in der Kryptografie wichtig, wo es darum geht, Zahlen zu finden, die mit einer gegebenen keinen gemeinsamen Teiler haben.
Euklidischer Algorithmus: Brauchen größere Zahlen mehr Runden?
Nein, und die Tabelle unten macht das greifbar. 1.000.000 und 999.998 sind in zwei Runden fertig, während 610 und 377 — je drei Stellen — dreizehn Runden brauchen. Viele Runden erzwingt nicht die Größe, sondern ein langsames Schrumpfen, und am langsamsten schrumpfen aufeinanderfolgende Fibonacci-Zahlen, bei denen jeder Rest dicht beim Divisor liegt. Dieses Ergebnis ist der Satz von Lamé, und er setzt der Rundenzahl eine Grenze, die nur mit der Stellenzahl wächst — deshalb gilt das Verfahren als schnell.
Worin unterscheidet sich das vom Faktorisieren beider Zahlen?
Faktorisieren ist deutlich mehr Arbeit, und diese Seite macht sie nie. Um 1.071 durch Ausprobieren zu faktorisieren, müssten Sie alle Teiler bis zu seiner Quadratwurzel testen, also bis 32; der Algorithmus dagegen teilt eine Zahl durch eine, die er schon hält, und ist nach drei Runden fertig. Bei kleinen Zahlen wie diesen ist der Unterschied unsichtbar, aber das Faktorisieren wird mit wachsenden Zahlen dramatisch schwerer, während der euklidische Algorithmus es kaum merkt. Dieser Abstand ist der ganze Grund, warum er noch gelehrt wird — und er ist auch der Grund, warum die Antwort oben aus der Schleife kommt und nicht aus einer zweiten Rechnung: Beides zu rechnen hieße zu riskieren, dass die gedruckten Schritte der Zahl darüber widersprechen.

Quellen

Verwandte Rechner

GGT-RechnerGemeinsame Teiler von zwei bis zehn Zahlen, und der größte.KGV-RechnerDie ersten vier gemeinsamen Vielfachen mehrerer Zahlen.Divisionsrest-RechnerQuotient und Rest – nach beiden Vorzeichenregeln.Sortier-RechnerSortiert eine Zahlenliste und zeigt kleinste und größte.Modulo-RechnerRest, der nie negativ wird – egal welche Vorzeichen.