Mit Google fortfahren
Euklidischer Algorithmus: ggT sicher berechnen
Mit dem euklidischen Algorithmus findest du den größten gemeinsamen Teiler zweier positiver natürlicher Zahlen, ohne beide Zahlen in Primfaktoren zu zerlegen. Du teilst wiederholt mit Rest. Der Divisor der letzten Division mit Rest 0 ist der ggT. Nur wenn vorher ein positiver Rest entstanden ist, ist dieser Divisor zugleich der letzte Rest ungleich null.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Was suchst du überhaupt?
Der größte gemeinsame Teiler, kurz ggT, ist die größte positive natürliche Zahl, die beide Ausgangszahlen ohne Rest teilt.
Größter gemeinsamer Teiler
Für positive natürliche Zahlen $a$ und $b$ bezeichnet $\operatorname{ggT}(a,b)$ den größten positiven Teiler, den $a$ und $b$ gemeinsam haben.
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$ der Dividend, $b$ der Divisor, $q$ der ganzzahlige Quotient und $r$ der Rest. Entscheidend ist: Der Rest ist stets kleiner als der Divisor.
Wie läuft der Algorithmus ab?
Beginne mit zwei positiven natürlichen Zahlen.
- Schreibe die größere Zahl als Dividend und die kleinere als Divisor.
- Führe eine Division mit Rest aus.
- Ist der Rest nicht null, wird der alte Divisor zum neuen Dividenden und der Rest zum neuen Divisor.
- Wiederhole die Division, bis der Rest null ist.
- Lies den ggT ab: Er ist der Divisor der letzten Division mit Rest 0. Wenn zuvor ein positiver Rest entstanden ist, ist dieser Divisor zugleich der letzte Rest ungleich null.
Beim Übergang zur nächsten Zeile wird aus dem Paar (Dividend, Divisor) das Paar (alter Divisor, alter Rest).
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$.
Wie sieht eine vollständige Rechnung aus?
Bestimme $\operatorname{ggT}(174,102)$.
Wir teilen wiederholt mit Rest:
$$174=1\cdot102+72$$
$$102=1\cdot72+30$$
$$72=2\cdot30+12$$
$$30=2\cdot12+6$$
$$12=2\cdot6+0$$
Die Reste sind $72,30,12,6,0$. In der letzten Division mit Rest 0 ist 6 der Divisor; hier ist 6 zugleich der letzte Rest ungleich null. Daher gilt:
$$\operatorname{ggT}(174,102)=6$$
Zur Kontrolle: $174=29\cdot6$ und $102=17\cdot6$. Die 6 teilt also wirklich beide Ausgangszahlen ohne Rest.
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?
Warum funktioniert und endet das Verfahren?
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)$$
In der letzten Zeile ist der Rest 0. Dann ist der letzte Divisor selbst der größte gemeinsame Teiler. Weil der ggT in allen Schritten gleich geblieben ist, ist er auch der ggT der Ausgangszahlen.
Der Algorithmus endet für positive natürliche Zahlen: Jeder neue Rest ist kleiner als der vorherige Divisor. Eine streng fallende Folge nichtnegativer ganzer Zahlen kann nicht unendlich weitergehen. Schließlich entsteht Rest 0.
Ist der Divisor der letzten Division mit Rest 0 gleich 1, dann haben die Ausgangszahlen außer 1 keinen gemeinsamen positiven Teiler. Sie heißen teilerfremd.
Wie setzt du den ggT in einer Sachaufgabe ein?
Zwei Stoffbahnen sind 413 cm und 295 cm lang. Beide sollen ohne Rest in möglichst lange, gleich lange Stücke geschnitten werden. Die gesuchte Stücklänge muss beide Bahnlängen teilen und soll möglichst groß sein – gesucht ist also der ggT.
$$413=1\cdot295+118$$
$$295=2\cdot118+59$$
$$118=2\cdot59+0$$
Damit ist $\operatorname{ggT}(413,295)=59$. Jedes Stück ist 59 cm lang.
Plausibilitätsprüfung: $413=7\cdot59$ und $295=5\cdot59$. Beide Stoffbahnen gehen ohne Rest auf, und die Stücklänge teilt beide Längen.
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.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Euklidischer Algorithmus
- Ziel: größten gemeinsamen Teiler finden
- Schritt: Division mit Rest
- Wechsel: alter Divisor und Rest
- Ende: Rest 0
- Ergebnis: Divisor der letzten Division mit Rest 0
- Kontrolle: Ergebnis teilt beide Ausgangszahlen
- Begründung: gemeinsame Teiler bleiben erhalten
- Sonderfall: ggT 1 bedeutet teilerfremd
Abschluss-Check
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.