Über 1,6 Millionen Schüler*innen nutzen sofatutor!
  • 93%

    haben mit sofatutor ihre Noten in mindestens einem Fach verbessert

  • 94%

    verstehen den Schulstoff mit sofatutor besser

  • 92%

    können sich mit sofatutor besser auf Schularbeiten vorbereiten

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!

Video abspielen
Du willst ganz einfach ein neues Thema lernen
in nur 12 Minuten?
Du willst ganz einfach ein neues
Thema lernen in nur 12 Minuten?
  • Das Mädchen lernt 5 Minuten mit dem Computer 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.
  • Das Mädchen übt 5 Minuten auf dem Tablet 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.
  • Das Mädchen stellt fragen und nutzt dafür ein Tablet 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.
Teste dein Wissen zum Thema Euklidischer Algorithmus – Bestimmung des ggT

Was ist der euklidische Algorithmus?

1/5
Bereit für eine echte Prüfung?

Das Ggt Bestimmen Quiz besiegt 60% der Teilnehmer! Kannst du es schaffen?

Quiz starten
Bewertung

Ø 3.5 / 43 Bewertungen
Die Autor*innen
Avatar
Sabine Blumenthal
Euklidischer Algorithmus – Bestimmung des ggT
lernst du in der 5. Klasse - 6. Klasse

Grundlagen zum Thema Euklidischer Algorithmus – Bestimmung des ggT

Euklidischer Algorithmus – Definition

Der euklidische Algorithmus ist ein Verfahren zur Bestimmung des größten gemeinsamen Teilers (ggT\text{ggT}) zweier natürlicher Zahlen. Entwickelt wurde dieser Algorithmus vom griechischen Mathematiker Euklid. Der ggT\text{ggT} zweier natürlicher Zahlen, die kleiner als 100100 sind, lässt sich noch vergleichsweise einfach bestimmen. Bei größeren Zahlen kann der euklidische Algorithmus helfen, den ggT\text{ggT} 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 aa ohne Rest die Zahl bb und die Zahl cc, dann teilt aa auch die Summe und die Differenz aus bb und cc (für b>cb>c) ohne Rest. Zur Verdeutlichung dient folgendes Beispiel:

  • 7217 \mid 21, also 77 ist ein Teiler von 2121.
  • 7707 \mid 70, 77 ist ebenfalls ein Teiler von 7070.
  • 7(21+70)7 \mid (21+70) und 7(7021)7 \mid (70-21) bedeutet demnach, dass 77 auch die Summe sowie die Differenz aus 7070 und 2121 teilt, denn (70+21):7=91:7=13(70+21):7=91:7=13 und (7021):7=49:7=7(70-21):7=49:7=7.

Der Teiler größerer Zahlen lässt sich jedoch nicht immer so leicht herausfinden. Hier hilft der euklidische Algorithmus.

ggT\text{ggT}: Algorithmus allgemein
Es gibt zwei Varianten, mittels des euklidischen Algorithmus den ggT\text{ggT} 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:

  • 1.1. Schritt: Ziehe die kleinere Zahl von der größeren Zahl ab.
  • 2.2. Schritt: Wiederhole Schritt 11 so lange, bis der Wert der Differenz kleiner als der Subtrahend ist.
  • 3.3. Schritt: Ziehe dann den Wert der Differenz vom Subtrahenden ab.
  • 4.4. Schritt: Die Schritte 11 bis 33 so oft wiederholen, bis Differenz und Subtrahend gleich sind. Das ist der gesuchte ggT\text{ggT}.

Bei der Division geht man folgendermaßen vor:

  • 1.1. Schritt: Teile die größere durch die kleinere Zahl (Division mit Rest).
  • 2.2. Schritt: Teile den Divisor der ersten Rechnung durch den entstandenen Rest.
  • 3.3. Schritt: Wiederhole die ersten beiden Schritte, bis bei der Division kein Rest mehr bleibt. Der letzte Divisor ist der gesuchte ggT\text{ggT}.

Beispiele – Wie bestimmt man den ggT für ggT:(360;105)

Für die Subtraktion kann man folgendermaßen vorgehen:

360105=255255105=150150105=4545<10510545=606045=1515<454515=303015=15ggT(360;105)=15\begin{array}{rcrcrcl} 360&-&105&=&255&&\\ 255&-&105&=&150&&\\ 150&-&105&=&45&\vert&45<105\\ 105&-&45&=&60&&\\ 60&-&45&=&15&\vert&15<45\\ 45&-&15&=&30&&\\ 30&-&\underline{15}&=&\underline{15}&\vert&\text{ggT}(360;105)=15 \end{array}

Wird für das Verfahren die Division verwendet, geht man so vor:

360:105=3Rest 45105:45=2Rest 1545:15=3Rest 0ggT(360;105)=15\begin{array}{rcrcrcl} 360&:&105&=&3&\vert&\text{Rest}~45\\ 105&:&45&=&2&\vert&\text{Rest}~15\\ 45&:&\underline{15}&=&3&\vert&\text{Rest}~\underline{0}\\ &&&&&&\text{ggT}(360;105)=15 \end{array}

ggT\text{ggT} von 10711071 und 10291029

1079:1029=1Rest 421029:42=24Rest 2142:21=2Rest 0ggT(1071;1029)=21\begin{array}{rcrclrl} 1079&:&1029&=&1&\vert&\text{Rest}~42\\ 1029&:&42&=&24&\vert&\text{Rest}~21\\ 42&:&\underline{21}&=&2&\vert&\text{Rest}~\underline{0}\\ &&&&&&\text{ggT}(1071;1029)=21 \end{array}

Teste dein Wissen zum Thema Ggt Bestimmen!

1.215.161 Schülerinnen und Schüler haben bereits unsere Übungen absolviert. Direktes Feedback, klare Fortschritte: Finde jetzt heraus, wo du stehst!

Vorschaubild einer Übung

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 ggT\text{ggT} 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 ggT\text{ggT} ü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!

8 Kommentare
  1. voll gut

    Von EliciaAndRabbits, vor mehr als einem Jahr
  2. Nice

    Von J Weiland, vor mehr als 3 Jahren
  3. Eukulid war meine erste Briefmarke bei der lernsafari

    Von Zobair1, vor mehr als 4 Jahren
  4. 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😁

    Von Ingo S., vor mehr als 6 Jahren
  5. cool

    Von Npw1895, vor mehr als 8 Jahren
Mehr Kommentare

Euklidischer Algorithmus – Bestimmung des ggT Übung

Du möchtest dein gelerntes Wissen anwenden? Mit den Aufgaben zum Video Euklidischer Algorithmus – Bestimmung des ggT kannst du es wiederholen und üben.
30 Tage kostenlos testen
Mit Spaß Noten verbessern
und vollen Zugriff erhalten auf

9.256

sofaheld-Level

6.600

vorgefertigte
Vokabeln

8.174

Lernvideos

38.660

Übungen

33.472

Arbeitsblätter

24h

Hilfe von Lehrkräften

laufender Yeti

Inhalte für alle Fächer und Klassenstufen.
Von Expert*innen erstellt und angepasst an die Lehrpläne der Bundesländer.

30 Tage kostenlos testen

Testphase jederzeit online beenden