30 Tage kostenlos testen:
Mehr Spass am Lernen.

Überzeugen Sie sich von der Qualität unserer Inhalte.

Euklidischer Algorithmus – Bestimmung des ggT 07:05 min

Textversion des Videos

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!

5 Kommentare
  1. 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 9 Monaten
  2. cool

    Von Npw1895, vor mehr als 2 Jahren
  3. Lieber Andreradloff1983! Du musst beachten, dass die Teilbarkeitsregeln und also auch der Euklidische Algorithmus nur für das Rechnen mit natürlichen Zahlen gelten. Und so entsteht der Rest 45 bei der Division von 360 : 105 => Die 105 passt genau dreimal in die 360 hinein. Also, 3 mal 105 = 315. Die Differenz (der Unterschied) zwischen 315 und 360 beträgt genau 45. Du hast sozusagen ohne Rest geteilt und deshalb eine Dezimalzahl (Kommazahl) als Ergebnis erhalten. Wie gesagt, die Teilbarkeitsregeln gelten nur für natürliche Zahlen.

    Von Sabine Blumenthal, vor mehr als 4 Jahren
  4. Also wenn ich 360:105 rechne, dann kommt da gerundet 3,43 raus.
    Ich verstehe nicht wie man da auf einen Rest von 45 kommt. Der Rest sind doch die beiden letzten Zahlen hinter dem Komma? Oder habe ich da was falsch verstanden?

    Von Andreradloff1983, vor mehr als 4 Jahren
  5. Kann man diesen Rechenweg zu jeden natürlichen Zahlen anwenden?

    Von Sandra 7, vor mehr als 5 Jahren

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.

  • Ergänze die Erklärung zum euklidischen Algorithmus.

    Tipps

    Achte im 2. Schritt und 4. Schritt auf die Reihenfolge.

    Merke dir:

    Minuend $-$ Subtrahend $=$ Differenz

    Lösung

    Euklid von Alexandria war ein griechischer Mathematiker. Man vermutet, dass er im 3. Jahrhundert v. Chr. in Alexandria gelebt hat.

    Auf Euklid geht der hier vorgestellte Algorithmus zum Bestimmen eines größten gemeinsamen Teilers zweier Zahlen zurück. Er verwendet dabei die Summenregel für die Teilbarkeit: Wenn zwei Zahlen einen gemeinsamen Teiler haben, dann teilt dieser Teiler auch die Summe sowie die Differenz der beiden Zahlen.

    Ein Algorithmus ist eine Abfolge von immer gleichen Rechenschritten. Schließlich soll der Algorithmus zu einem Ergebnis, hier dem größten gemeinsamen Teiler zweier Zahlen, führen.

    1. Schritt: Bilde die Differenz der beiden Zahlen. Ziehe hierfür von der größeren die kleinere ab. Du erhältst dann $360-105=255$.

    2. Schritt: Wiederhole den 1. Schritt so lange, bis der Rest, sprich die Differenz, kleiner ist als der Subtrahend:

    • $255-105=150$
    • $150-105=45$: Du siehst, die Differenz $45$ ist kleiner als der Subtrahend $105$.
    3. Schritt: Ziehe von dem Subtrahenden die Differenz ab, also $105-45=60$.

    4. Schritt: Wiederhole die ersten drei Schritte so lange, bis der Subtrahend und die Differenz übereinstimmen:

    • $60-45=15$
    • $45-15=30$
    • $30-15=15$: Nun stimmen Subtrahend $15$ und Differenz $15$ überein. Dies ist der gesuchte größte gemeinsame Teiler.
    Es ist also ggT$(360;105)=15$.

  • Gib die Summenregel für die Teilbarkeit an.

    Tipps

    Prüfe jede der obigen Aussagen an dem gegebenen Beispiel. Ist die Aussage für dieses Beispiel falsch, so kann die Aussage auch im Allgemeinen nicht gelten.

    Du kannst $21$ nicht ohne Rest durch $14$ dividieren.

    Es ist $7\cdot 7=49$ sowie $13\cdot 7=91$.

    • $70-21 =49$ und
    • $70+21=91$
    Lösung

    Die Zahl $7$ teilt sowohl $21$ also auch $70$. Sie ist also ein gemeinsamer Teiler. Es gilt die Summenregel. Diese besagt:

    Wenn zwei Zahlen einen gemeinsamen Teiler haben, dann teilt dieser gemeinsame Teiler auch die Summe sowie die Differenz der beiden Zahlen.

    Übrigens: Der gemeinsame Teiler teilt natürlich auch das Produkt, aber im Allgemeinen nicht den Quotienten der beiden Zahlen.

    Schauen wir uns das Beispiel an:

    • Die Summe der beiden Zahlen ist $70+21=91$ und es gilt $7\mid 91$, da $13\cdot 7=91$ ist.
    • Das Doppelte von $7$ ist $14$ und $14$ teilt $21$ nicht.
    • Der Quotient der beiden Zahlen ist $\frac{70}{21} = 3{,}\overline{3}$. Da dies keine natürliche Zahl ist, hat diese Zahl keine Teiler.
    • Die Differenz der beiden Zahlen ist $70-21 =49$ und es gilt $7\mid 49$, da $7\cdot 7=49$ ist.
  • Bestimme den größten gemeinsamen Teiler der beiden Zahlen.

    Tipps

    Merke dir:

    Dividend $:$ Divisor $=$ Quotient

    Beim Teilen mit Rest schaust du immer, wie oft der Divisor „ganz“ in den Dividenden passt. Schau dir $45:12$ als Beispiel an:

    • Es ist $3\cdot 12=36$ und $45-36=9$.
    • So erhältst du $45:12=3$ Rest $9$.

    Der Rest ist immer kleiner als der Divisor.

    Lösung

    Euklid hat ganz schön viel für die Mathematik getan. Dazu gehört auch ein Algorithmus zur Bestimmung eines größten gemeinsamen Teilers mit Hilfe der Division.

    1. Schritt: Dividiere die größere Zahl durch die kleinere. Ist dies ohne Rest möglich, so ist die kleinere Zahl der größte gemeinsame Teiler. Hier erhältst du $360:105=3$, es bleibt ein Rest von $360-3\cdot 105=360-315=45$.

    2. Schritt: Teile nun den Divisor, also $105$, durch den Rest, hier $45$. Du rechnest $105:45=2$ Rest $15$.

    3. Schritt: Wiederhole nun den 2. Schritt so lange, bis du einen Rest $0$ erhältst. Dies ist im nächsten Schritt der Fall. Dieser ergibt $45:15=3$ Rest $0$.

    Der letzte Divisor, hier die $15$, ist der gesuchte größte gemeinsame Teiler:

    ggT$(360;105)=15$.

  • Vergleiche die beiden euklidischen Algorithmen.

    Tipps

    Der euklidische Algorithmus mit Subtraktion beginnt so:

    • $702-318=384$
    • $384-318=66$
    • $318-66=252$
    Dies sind bereits $3$ Rechnungen.

    Der Euklidische Algorithmus mit Division beginnt so:

    • $702:318=2$ Rest $66$
    • $318:66=4$ Rest $54$
    Dies sind bereits $2$ Rechnungen.

    Bei dem euklidischen Algorithmus Subtraktion werden $7$ Rechnungen mehr durchgeführt als bei dem mit der Division.

    Lösung

    Ist das Bestimmen des größten gemeinsamen Teilers mit Hilfe der Subtraktion tatsächlich so viel aufwendiger als mit der Division? Das überprüfen wir nun einmal an einem Beispiel. Es soll ggT$(318;702)$ bestimmt werden.

    Beginne mit der Subtraktion. Du rechnest so lange, bis Subtrahend und Differenz in einer Rechnung übereinstimmen. Das ist dann der gesuchte größte gemeinsame Teiler.

    • $702-318=384$
    • $384-318=66$
    • $318-66=252$
    • $252-66=186$
    • $186-66=120$
    • $120-66=54$
    • $66-54=12$
    • $54-12=42$
    • $42-12=30$
    • $30-12=18$
    • $18-12=6$
    • $12-6=6$
    Puh, geschafft. Das sind $12$ Rechnungen. Der größte gemeinsame Teiler ist $6$.

    Na, mal schauen, ob das mit der Division schneller geht:

    • $702:318=2$ Rest $66$
    • $318-66=4$ Rest $54$
    • $66:54=1$ Rest $12$
    • $55:12=4$ Rest $6$
    • $12:6=2$ Rest $0$
    ggT$(318;702)=6$ ist gefunden. Hier benötigst du $5$ Rechnungen.

    Der erste Algorithmus braucht also mehr Schritte. Vielleicht fällt er dir dennoch leichter? Rechne einige weitere Aufgaben und entscheide für dich, welchen Algorithmus du lieber benutzt.

  • Ermittle den größten gemeinsamen Teiler von $60$ sowie $96$ mit Hilfe von Differenzen.

    Tipps

    Hier siehst du noch einmal das allgemeine Vorgehen:

    1. Schritt: Bilde die Differenz der beiden Zahlen. Ziehe hierfür von der größeren die kleinere ab.

    2. Schritt: Wiederhole den 1. Schritt so lange, bis die Differenz kleiner ist als der Subtrahend.

    3. Schritt: Ziehe von dem Subtrahenden die Differenz ab.

    4. Schritt: Wiederhole die ersten drei Schritte so lange, bis der Subtrahend und die Differenz übereinstimmen.

    Am Ende dieses Algorithmus hast du den größten gemeinsamen Teiler gefunden.

    Lösung

    In dieser Aufgabe kannst du den Algorithmus, der auf Differenzen basiert, an etwas kleineren Zahlen üben. Dieser Algorithmus funktioniert bei beliebigen natürlichen Zahlen.

    1. Schritt: Bilde die Differenz der beiden Zahlen. Ziehe hierfür von der größeren die kleinere ab:

    $96-60=36$

    2. Schritt: Wiederhole den 1. Schritt so lange, bis die Differenz kleiner ist als der Subtrahend. Dies ist hier bereits der Fall.

    3. Schritt: Subtrahiere nun vom Subtrahenden die Differenz.

    Du erhältst dann $60-36=24$.

    4. Schritt: Wiederhole die ersten drei Schritte so lange, bis der Subtrahend und die Differenz übereinstimmen.

    • $36-24=12$
    • $24-12=12$
    Der Subtrahend und die Differenz stimmen überein. Beide sind $12$. Dies ist der gesuchte größte gemeinsame Teiler. Es gilt:

    ggT$(60;96)=12$

  • Leite den größten gemeinsamen Teiler von $48$ und $246$ durch Division her.

    Tipps

    Teile immer den Divisor durch den vorherigen Rest. Wenn das Ergebnis $0$ ist, ist der Divisor dieser Rechnung der größte gemeinsame Teiler.

    Die Bezeichnungen bei der Division lauten wie folgt:

    Dividend $:$ Divisor $=$ Quotient

    Hier siehst du ein Beispiel für die Ermittlung des größten gemeinsamen Teilers:

    Finde den größten gemeinsamen Teiler von $412$ und $36$.

    • $412:36 = 11$ Rest $16$
    • $36:16 = 2$ Rest $4$
    • $16:4 = 4$ Rest $0$
    Der größte gemeinsame Teiler von $412$ und $36$ ist $4$.

    Lösung

    Hier berechnest du den größten gemeinsamen Teiler von $246$ und $48$ mit Hilfe der Division:

    1. Schritt: Dividiere $246:48=5$ mit einem Rest von $246-5\cdot 48=246-240=6$.

    2. Schritt: Teile nun den Divisor ($48$) durch den Rest ($6$). Du erhältst $48:6=8$ Rest $0$.

    Du bist bereits fertig, da der Rest $0$ ist. Der letzte Divisor ist der gesuchte größte gemeinsame Teiler:

    ggT$(48;246)=6$