Der Euklidische Algorithmus

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.

   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.

   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.

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.

   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.

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

   a.) 9 und 30

   b.) 226 und 904

   c.) 1215 und 2115

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

Hilfekarten

...in der Geometrie

Gruppe 1

Gruppe 2

Gruppe 3

Der Euklidische Algorithmus: Herunterladen [odt][466 KB]

Der Euklidische Algorithmus: Herunterladen [pdf][857 KB]

Weiter zu Hilfekarten