Euklidischer Algorithmus – Bestimmung des ggT

Euklidischer Algorithmus – Bestimmung des ggT Übung

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