Der Euklidische Algorithmus – Lösungen

Entdecker-Aufträge:

1. Betrachte die Zahlen 56 und 32. Es gilt ggT(32; 56) = 8. Wir zerlegen nun beide Ausgangszahlen mithilfe ihres ggT und erhalten 32 = 4 · 8 und 56 = 7 · 8. Mithilfe dieser Zerlegungen kann man über die Differenz 56 – 32 aussagen, dass sie 3 · 8 sein muss, ohne sie explizit auszurechnen.

   a.) Begründe diese Aussage.

   56 − 32 = 7 · 8 − 4 · 8 = (7 − 4) · 8 = 3 · 8

   

   Oder anschaulich mit nebenstehender Abbildung: Die 8 wird als Maßzahl verwendet. Laut Vorgabe passt sie viermal in die 32 (dunkelgrau) und siebenmal in die 56 (hellgrau). Somit passt die 8 also dreimal in die Differenz von 56 und 32 (weiß).

   b.) Aus diesem Wissen folgt eine weitere Aussage: Die Differenz 56 – 32 ist ebenfalls durch 8 teilbar, d.h. der ggT von 56 und 32 teilt auch die Differenz 56 – 32. Begründe.

   Der ggT ist Teiler von beiden „Summanden“ (Minuend und Subtrahend), also kann er ausgeklammert werden. Somit lässt sich die Differenz als „Klammer mal 8 (=ggT)“ schreiben, wobei in der Klammer eine natürliche Zahl steht. Dies entspricht aber der Definition für die Teilbarkeit durch 8 (also den ggT), die Differenz ist also durch 8 (den ggT) teilbar.

   c.) Dieses Vorgehen funktioniert nicht nur für die Zahlen 56 und 32, sondern für beliebige Zahlen. Führe es an den Zahlenpaaren 25 und 35, 4 und 12 sowie 26 und 65 erneut durch.

   35 − 25 = 7 · 5 − 5 · 5 = (7 − 5) · 5 = 2 · 5

   12 − 4 = 3 · 4 − 1 · 4 = (3 − 1) · 4 = 2 · 4

   65 − 26 = 5 · 13 − 2 · 13 = (5 − 2) · 13 = 3 · 13

2. Darüber hinaus kann man zeigen, dass der ggT von 56 und 32 nicht nur „irgendein“ Teiler von 56 – 32 ist, sondern dass er sogar der ggT von 56 – 32 und 32 sein muss.

   a.)* Begründe diese Aussage.

   Wir wissen: Der ggT von 56 und 32 teilt 56 – 32.

   Sollte dies nicht der ggT von 56 – 32 und 32 sein, so müsste es einen größeren Teiler von 56 – 32 und 32 geben, als den ggT von 56 und 32. Da dieser Teiler in der Differenz 56 – 32 den Minuenden 32 teilt, muss er auch Teiler von 56 sein (nach dem entsprechenden Satz über die Teilbarkeit von Summen). Somit wäre er auch gemeinsamer Teiler von 56 und 32, der größer wäre als deren ggT – das ist nicht möglich (weil er sonst der ggT wäre).

   Also muss der ggT von 56 und 32 auch der ggT von 56 – 32 und 32 sein.

   b.) Diese Erkenntnis hat der griechische Mathematiker Euklid von Alexandria 325 v. Chr. In seinem Werk „Die Elemente“ weitergeführt. Er entwickelte daraus den sogenannten Euklidischen Algorithmus, mit dem man den ggT zweier Zahlen bestimmen kann. Am Beispiel der Zahlen 56 und 32 geht der Algorithmus so:

   ggT(56; 32) = ggT(24; 32) = ggT(24; 8) = ggT(16; 8) = ggT(8; 8) = 8

   Überlege dir, wie Euklid von links nach rechts in dieser „Kettengleichung“ vorgeht. Überprüfe dein Vorgehen an den Zahlenpaaren aus 1c.), indem du deren ggT mit dem gleichen Vorgehen bestimmst und mit den ggT-Werten aus deinen Lösungen von 1c.) abgleichst. Schreibe dann eine Anleitung, wie man auf diese Weise den ggT zweier beliebiger Zahlen bestimmen kann. Es liegen Hilfekärtchen bereit, falls du nicht weiterkommst.

   Euklid ersetzt immer die größere der beiden Zahlen durch die Differenz aus der größeren und der kleineren Zahl. Nach a.) verändert sich dadurch der ggT nicht. Am Schluss verbleibt ein ggT mit zwei gleichen Zahlen – dies ist der ggT der beiden Ausgangszahlen.

   Beispiele:

   ggT(35;25) = ggT(10;25) = ggT(10;15) = ggT(10;5) = ggT(5;5) = 5

   ggT(12;4) = ggT(8;4) = ggT(4;4) = 4

   ggT(65;26) = ggT(39;26) = ggT(13;26) = ggT(13;13) = 13

3. Führe den Euklidischen Algorithmus an den folgenden Zahlenpaaren durch.

   a.) 9 und 30

   ggT(9;30) = ggT(9;21) = ggT(9;12) = ggT(9;3) = ggT(6;3) = ggT(3;3) = 3

   b.) 226 und 904

   ggT(226;904 = ggT(226;678) = ggT(226;452) = ggT(226;226) = 226

   c.) 1215 und 2115

   ggT(1215;2115) = ggT(1215;900) = ggT(315;900)

   = ggT(315;585) = ggT(315;270) = ggT(45;270) = ggT(45;225)

   = ggT(45;180) = ggT(45;135) = ggT(45;90) = ggT(45;45) = 45

4. * Programmiere den Euklidischen Algorithmus so, dass der Anwender zwei Zahlen eingeben kann und den ggT als Ausgabe erhält.

   Lösungsdatei in Scratch: EuklidischerAlgorithmus.sb2 (Autor: Tom Schaller)

   Lösungsdatei im AppInventor: ggt_euklid.apk im Ordner 7_apps (Autorin: Monika Eisenmann)

Der Euklidische Algorithmus – Lösungen: Herunterladen [odt][112 KB]

Der Euklidische Algorithmus – Lösungen: Herunterladen [pdf][116 KB]

Weiter zu APPs