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\lt 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.

1. Schreibe die größere Zahl als Dividend und die kleinere als Divisor. Sind beide gleich, teilst du die Zahl durch sich selbst.
2. Führe eine Division mit Rest aus.
3. Ist der Rest nicht null, wird der alte Divisor zum neuen Dividenden und der Rest zum neuen Divisor.
4. Wiederhole die Division, bis der Rest null ist.
5. Lies den ggT ab: Er ist der Divisor der letzten Division mit Rest 0.

Wenn gleich die erste Division aufgeht, ist die kleinere Zahl bereits der ggT. Beispiel: $24=3\cdot8+0$, also ist $\operatorname{ggT}(24,8)=8$.

Bestimme $\operatorname{ggT}(174,102)$.

Achte bei jeder Zeile auf zwei Kontrollen:

• Stimmt die Gleichung aus Produkt und Rest?
• 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)$$

Bei Rest 0 betrachten wir auch das Paar $(b,0)$: Jede positive Zahl $b$ teilt 0, denn $0=0\cdot b$. Der größte gemeinsame Teiler von $b$ und 0 ist deshalb $b$ selbst. Weil die gemeinsamen Teiler bei jedem Schritt erhalten bleiben, ist dieser letzte Divisor auch der ggT der Ausgangszahlen.

Das Verfahren endet, weil die Divisoren bei jedem weiteren Schritt kleinere positive ganze Zahlen werden. Das kann nicht beliebig lange weitergehen: Irgendwann geht eine Division ohne Rest auf.

Stell dir vor: Zwei Stoffbahnen sind 413 cm und 295 cm lang. Beide sollen ohne Rest in möglichst lange, gleich lange Stücke geschnitten werden. Wir rechnen ohne Stoffverlust beim Schneiden. Die gesuchte Stücklänge muss beide Bahnlängen teilen und soll möglichst groß sein – gesucht ist also der ggT.

Jetzt du: ggT von 132 und 28

Führe den Algorithmus selbst aus. Entscheide danach, welche Lösung stimmt.

Typische Fehler vermeidest du so:

• Zu früh stoppen: Ein kleiner Rest ist noch nicht automatisch der ggT. Stoppe erst bei Rest 0.
• Falsches Zahlenpaar übernehmen: Nimm alten Divisor und alten Rest, nicht alten Dividend und Rest.
• Den Rest 0 als ggT nennen: Gesucht ist der Divisor der Division, die den Rest 0 liefert.
• Eine Sachfrage überlesen: „Möglichst groß und ohne Rest“ weist auf den ggT hin.

Du beherrschst das Verfahren, wenn du die Zahlenpaare korrekt weiterführst, erst bei Rest 0 stoppst, den Divisor dieser letzten Division als ggT abliest und dein Ergebnis an beiden Ausgangszahlen prüfst.