Euklidischer Algorithmus: ggT sicher berechnen

Der größte gemeinsame Teiler, kurz ggT, ist die größte positive natürliche Zahl, die beide Ausgangszahlen ohne Rest teilt. Bei 18 und 30 sind 1, 2, 3 und 6 gemeinsame Teiler. Der größte davon ist 6, also gilt \operatorname{ggT}(18,30)=6. Für den Algorithmus brauchst du die Division mit Rest: a=q\cdot b+r \quad\text{mit}\quad 0\le r<b Dabei ist a die Zahl, die du teilst (Dividend), und b die Zahl, durch die du teilst (Divisor). Der Quotient q sagt, wie oft b ganz in a hineinpasst. r bleibt als Rest übrig. Der Rest ist mindestens 0 und kleiner als der Divisor.

Beginne mit zwei positiven natürlichen Zahlen. Teile die größere Zahl mit Rest durch die kleinere. Sind beide gleich, teilst du die Zahl durch sich selbst. Ist der Rest nicht null, wird der alte Divisor zum neuen Dividenden und der Rest zum neuen Divisor. Das wiederholst du, bis der Rest null ist. Der ggT ist dann der Divisor dieser letzten Division. Geht schon die erste Division auf, ist die kleinere Zahl der ggT: Aus 24=3\cdot8+0 folgt \operatorname{ggT}(24,8)=8. Prüfe bei jeder Zeile zwei Dinge: Stimmt die Gleichung, und ist der Rest mindestens 0 und echt kleiner als der Divisor?

Betrachte einen einzelnen Schritt a=q\cdot b+r. Die Paare (a,b) und (b,r) haben dieselben gemeinsamen Teiler. Teilt eine Zahl sowohl a als auch b, dann teilt sie auch r=a-q\cdot b. Teilt eine Zahl sowohl b als auch r, dann teilt sie auch a=q\cdot b+r. Deshalb bleibt der ggT bei jedem Schritt gleich: \operatorname{ggT}(a,b)=\operatorname{ggT}(b,r) Am Ende steht das Paar (b,0). Jede positive Zahl b teilt 0, denn 0=0\cdot b. Der ggT von b und 0 ist also b selbst. Das Verfahren endet immer: Die Divisoren werden bei jedem Schritt kleinere positive ganze Zahlen, das geht nicht beliebig lange weiter.

Zwei Stoffbahnen sind 413 cm und 295 cm lang. Beide sollen ohne Rest in möglichst lange, gleich lange Stücke geschnitten werden, ohne Verlust beim Schneiden. Die Stücklänge muss beide Längen teilen und soll möglichst groß sein. Gesucht ist also der ggT. Typische Fehler vermeidest du so: Stoppe erst bei Rest 0, auch wenn ein Rest schon klein ist. Nimm immer alten Divisor und alten Rest, nicht alten Dividenden und Rest. Und nenne nicht den Rest 0 als ggT, sondern den Divisor dieser Division.