Ü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!

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.
Bewertung

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

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$.

  • 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$.

  • 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$.

  • 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.
  • 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.