Euklidischer Algorithmus – Bestimmung des ggT
Der euklidische Algorithmus ist eine Methode, um den größten gemeinsamen Teiler von zwei natürlichen Zahlen durch Subtraktion oder Division zu finden. Er wurde von Euklid entwickelt und ermöglicht es, den ggT auch bei größeren Zahlen schnell zu bestimmen. Interessiert? Dann lies weiter im Text!

in nur 12 Minuten? Du willst ganz einfach ein neues
Thema lernen in nur 12 Minuten?
-
5 Minuten verstehen
Unsere Videos erklären Ihrem Kind Themen anschaulich und verständlich.
92%der Schüler*innen hilft sofatutor beim selbstständigen Lernen. -
5 Minuten üben
Mit Übungen und Lernspielen festigt Ihr Kind das neue Wissen spielerisch.
93%der Schüler*innen haben ihre Noten in mindestens einem Fach verbessert. -
2 Minuten Fragen stellen
Hat Ihr Kind Fragen, kann es diese im Chat oder in der Fragenbox stellen.
94%der Schüler*innen hilft sofatutor beim Verstehen von Unterrichtsinhalten.
Grundlagen zum Thema Euklidischer Algorithmus – Bestimmung des ggT
Euklidischer Algorithmus – Definition
Der euklidische Algorithmus ist ein Verfahren zur Bestimmung des größten gemeinsamen Teilers () zweier natürlicher Zahlen. Entwickelt wurde dieser Algorithmus vom griechischen Mathematiker Euklid. Der zweier natürlicher Zahlen, die kleiner als sind, lässt sich noch vergleichsweise einfach bestimmen. Bei größeren Zahlen kann der euklidische Algorithmus helfen, den vergleichsweise schnell zu bestimmen.
Grundgedanke
Euklid machte sich bei der Entwicklung des Verfahrens die Summenregel der Teilbarkeit zweier Zahlen zunutze. Diese besagt: Teilt eine Zahl ohne Rest die Zahl und die Zahl , dann teilt auch die Summe und die Differenz aus und (für ) ohne Rest. Zur Verdeutlichung dient folgendes Beispiel:
- , also ist ein Teiler von .
- , ist ebenfalls ein Teiler von .
- und bedeutet demnach, dass auch die Summe sowie die Differenz aus und teilt, denn und .
Der Teiler größerer Zahlen lässt sich jedoch nicht immer so leicht herausfinden. Hier hilft der euklidische Algorithmus.
: Algorithmus allgemein
Es gibt zwei Varianten, mittels des euklidischen Algorithmus den zweier Zahlen zu bestimmen. Zum einen kann der Algorithmus durch Subtraktion und zum anderen durch Division der beiden zu untersuchenden Zahlen durchgeführt werden.
Bei der Subtraktion wird wie folgt vorgegangen:
- Schritt: Ziehe die kleinere Zahl von der größeren Zahl ab.
- Schritt: Wiederhole Schritt so lange, bis der Wert der Differenz kleiner als der Subtrahend ist.
- Schritt: Ziehe dann den Wert der Differenz vom Subtrahenden ab.
- Schritt: Die Schritte bis so oft wiederholen, bis Differenz und Subtrahend gleich sind. Das ist der gesuchte .
Bei der Division geht man folgendermaßen vor:
- Schritt: Teile die größere durch die kleinere Zahl (Division mit Rest).
- Schritt: Teile den Divisor der ersten Rechnung durch den entstandenen Rest.
- Schritt: Wiederhole die ersten beiden Schritte, bis bei der Division kein Rest mehr bleibt. Der letzte Divisor ist der gesuchte .
Beispiele – Wie bestimmt man den ggT für ggT:(360;105)
Für die Subtraktion kann man folgendermaßen vorgehen:
Wird für das Verfahren die Division verwendet, geht man so vor:
von und
Euklidischer Algorithmus –Verwendung
An den Beispielen ist zu erkennen, dass mit dem euklidischen Algorithmus auch der größte gemeinsame Teiler zweier vierstelliger und auch größerer Zahlen verhältnismäßig schnell bestimmt werden kann, wenn die Grundlagen der Division mit Rest beherrscht werden.
Einschränkungen des Algorithmus
Dieses Verfahren kann jedoch nur für die Bestimmung des von zwei Zahlen genutzt werden. Bei drei und mehr Zahlen ist ein anderes Verfahren zu verwenden.
Im Falle mehrerer Zahlen bietet sich beispielsweise das Finden des über die Primfaktorzerlegung oder über die Betrachtung der Teilermengen an.
Transkript Euklidischer Algorithmus – Bestimmung des ggT
Hallo, da bin ich wieder, eure Sabine Blumenthal!In diesem Video erkläre ich dir den euklidischen Algorithmus. Du lernst, was das ist, und du lernst die Rechenverfahren von Euklid kennen. Das solltest du bereits wissen: Die Summenregel der Teilbarkeit Natürlicher Zahlen, was ein ggT ist, du solltest die Subtraktion Natürlicher Zahlen können und auch die Division Natürlicher Zahlen. Der euklidische Algorithmus, was ist das überhaupt? Nun, das ist eine Möglichkeit, den ggT von zwei Zahlen zu bestimmen. Es ist ein Rechenverfahren, welches vor mehr als 2000 Jahren von Euklid erdacht wurde. Den Namen Euklid solltest du dir schon einmal merken. Hier siehst du ein Bild von Euklid. Er lebte ungefähr um 300 vor Christus, also vor mehr als 2000 Jahren. Er war ein griechischer Mathematiker und hat sich unter anderem dieses Verfahren ausgedacht, um den ggT von zwei Zahlen zu bestimmen. Euklid nutzte für seinen Algorithmus die Summenregel der Teilbarkeit. Erinnere dich an diese Regel zur Teilbarkeit Natürlicher Zahlen. Sie lautet: Wenn zwei Zahlen einen gemeinsamen Teiler haben, wie hier im Beispiel die 21 und die 70, dann teilt dieser gemeinsame Teiler auch die Summe beziehungsweise die Differenz der zwei Zahlen. In unserem Beispiel ist die sieben also auch ein Teiler der Summe 21 plus 70 beziehungsweise der Differenz 70 minus 21. Sieben ist ein Teiler von 91, weil 713=91 ist und sieben ist ein Teiler von 49, weil 77=49 ist. Nun ist das Finden gemeinsamer Teiler bei Zahlen im Bereich des kleinen Einmaleins, also bis etwa zur 100, nicht so schwierig. Bei großen Zahlen kann das Finden von gemeinsamen Teilern oder des ggT sehr mühsam sein. In einem solchen Fall kann uns der von Euklid gefundene Algorithmus helfen. Algorithmus bedeutet, dass gleiche Handlungen in einer bestimmten Reihenfolge immer wiederholt werden. Euklid wiederholte immer die gleiche Folge von Rechenschritten, deshalb bedeutet Algorithmus hier soviel wie Rechenkette. Schauen wir uns die Abfolge der Rechenschritte an einem Beispiel an: Wir wollen den ggT von 360 und 105 bestimmen. Damit du die einzelnen Schritte gut nachvollziehen kannst, habe ich die Subtrahenden immer in rot und die Ergebnisse in grün geschrieben. Ich spreche in der Erklärung auch von roten und grünen Zahlen. Das ist mathematisch zwar nicht so ganz exakt, aber so kannst du den Rechenweg besser nachvollziehen. Doch nun endlich zu unserer Rechenkette. Der erste Schritt: Ziehe die kleinere Zahl von der größeren ab. Du rechnest also 360 minus 105 und erhältst 255. Der zweite Schritt lautet: wiederhole den ersten Schritt so lange, bis der Rest, also die grüne Zahl, kleiner als die rote Zahl ist. Im dritten Schritt heißt es: ziehe nun den Rest, also die grüne Zahl, von dem letzten Subtrahenden, also der roten Zahl, ab. Hier ist 45 kleiner als 105. Also rechnest du jetzt 105 minus 45 und erhältst 60. Du vergleichst wieder die grüne und die rote Zahl. Ist die grüne Zahl größer als die rote, beginnst du wieder bei Schritt eins und das Ganze geht von vorne los. Der vierte Schritt ist ganz einfach. Wiederhole die Schritte eins bis drei so lange, bis die rote und die grüne Zahl gleich groß sind. Wenn du das erreicht hast, dann hast du den ggT gefunden. Rote Zahl gleich grüne Zahl, das heißt, diese Zahl ist der gesuchte ggT. 15 ist also der ggT von 360 und 105. Dieses Verfahren mit Subtraktionen erleichtert zwar das Finden des ggT von zwei großen Zahlen, aber es ist doch manchmal ziemlich lang und zeitaufwendig. Und du ahnst es schon, auch dieses Verfahren kann man abkürzen. Dank Herrn Euklid gibt es auch einen Algorithmus mit Divisionen. Wir bleiben bei unserem Beispiel, den ggT von 360 und 105 zu bestimmen. Dann kannst du beide Verfahren besser miteinander vergleichen. Der erste Schritt heißt jetzt: teile die größere durch die kleinere Zahl. Du solltest jetzt also die Division mit Rest gut beherrschen. Teile also 360 durch 105, du erhältst drei und es bleibt ein Rest von 45, den ich in grün schreibe. Der zweite Schritt lautet: teile die kleinere, also die rote, Zahl durch den Rest, also durch die grüne Zahl. 105 geteilt durch 45 ist gleich zwei, denn zweimal 45 ist 90, und es bleibt ein Rest von 15. Der dritte Schritt sagt: wiederhole Schritt zwei solange, bis bei der Division der Rest null bleibt. 45/15=3, Rest null. Damit ist der Algorithmus beendet, du hast den ggT gefunden. Die letzte Zahl, durch die du geteilt hast, also der letzte Divisor oder ganz einfach die letzte rote Zahl, ist dein gesuchter ggT. Und nun gibts zum euklidischen Algorithmus noch eine kurze Zusammenfassung: Der bedeutende griechische Mathematiker Euklid fand vor über 2000 Jahren ein Rechenverfahren heraus, um den ggT zweier Zahlen zu bestimmen, den nach ihm benannten Euklidischen Algorithmus. Euklid fand sogar zwei Möglichkeiten seines Algorithmus heraus: eine Subtraktionskette und eine Divisionskette. Na, hast du trotz der vielen Zahlen und Rechenschritte alles gut verstehen können? Prima! Dann tschüss, bis zum nächsten Mal!
Euklidischer Algorithmus – Bestimmung des ggT Übung
-
Ergänze die Erklärung zum euklidischen Algorithmus.
-
Bestimme den größten gemeinsamen Teiler der beiden Zahlen.
-
Ermittle den größten gemeinsamen Teiler von sowie mit Hilfe von Differenzen.
-
Leite den größten gemeinsamen Teiler von und durch Division her.
-
Gib die Summenregel für die Teilbarkeit an.
-
Vergleiche die beiden euklidischen Algorithmen.
9.256
sofaheld-Level
6.600
vorgefertigte
Vokabeln
8.174
Lernvideos
38.660
Übungen
33.472
Arbeitsblätter
24h
Hilfe von Lehrkräften

Inhalte für alle Fächer und Klassenstufen.
Von Expert*innen erstellt und angepasst an die Lehrpläne der Bundesländer.
Testphase jederzeit online beenden
Beliebteste Themen in Mathematik
- Römische Zahlen
- Prozentrechnung
- Prozentrechnung - Übungen
- Primzahlen
- Geometrische Lagebezeichnungen
- Was ist eine Ecke?
- Rechteck
- Was ist eine Gleichung?
- Pq-Formel
- Binomische Formeln
- Trapez
- Volumen Zylinder
- Potenzgesetze – Übungen
- Umfang Kreis
- Zehnerzahlen vergleichen und ordnen – Übungen
- Quadrat
- Zahlen sortieren – Übungen
- Division
- Binomische Formeln – Übungen
- Raute
- Parallelogramm
- Ungleichungen – Übungen
- Polynomdivision
- Zahlen bis 1000 ordnen – Übungen
- Was Ist Eine Viertelstunde
- Terme mit Variablen aufstellen – Übungen
- Prisma
- Die Grundrechenarten – Übungen
- Mitternachtsformel
- Äquivalenzumformung
- Grundrechenarten Begriffe
- Größer Kleiner Zeichen
- Dreiecksarten
- Punkt-vor-Strich und Klammern-zuerst-Regel
- Aufbau von Dreiecken
- Quader
- Zahlen runden – Übungen
- Satz Des Pythagoras
- Ziffern und Stellenwerte – Übungen
- Dreieck Grundschule
- Koordinatensystem – Übungen
- Erste Binomische Formel
- Kreis
- Trigonometrie
- Trigonometrische Funktionen
- Standardabweichung
- Quadratische Gleichungen – Übungen
- Flächeninhalt
- Termumformungen – Übungen
- Volumen Kugel
voll gut
Nice
Eukulid war meine erste Briefmarke bei der lernsafari
Super Video! Versteh nicht warum das nur 3,5 Sternchen hat! Ich habs selber ausgerechnet mit den Zahlen 235 und 721, aber die sind teilerfremd. Das war mit - . Geteilt hab ich mit den Zahlen 214 und 102, und deren ggT ist 2. Nicht so spektakulär😁
cool