Euklidischer Algorithmus
Wie findet man den Größter gemeinsamer Teiler|ggT von 1071 und 462 ? Alle Teiler auflisten dauert ewig, die Primfaktorzerlegung ist bei großen Zahlen mühsam. Der Grieche Euklid hat schon vor über 2300 Jahren einen viel schnelleren Weg aufgeschrieben – einen der ältesten Algorithmen der Welt. Die Idee als Bild: Ein Rechteck 42 times 22 soll mit möglichst großen, gleichen Quadraten ausgelegt werden. Wir schneiden immer das größte Quadrat ab, das noch passt: Am Ende geht alles glatt mit Quadraten der Seite 2 auf – und 2 ist genau text{ggT}(42, 22) . Grundgedanke Ein gemeinsamer Teiler von a und b teilt auch den Rest von a : b . Deshalb gilt: text{ggT}(a, b) = text{ggT}(b, r) qquad (r = text{Rest von } a : b) Die Zahlen werden so immer kleiner, bis es aufgeht. Jede Zeile ist eine Division mit Rest in der Form a = q cdot b + r . Bestimme text{ggT}(42, 22) . 42 = 1 cdot 22 + 20 22 = 1 cdot 20 + mathbf{2} 20 = 10 cdot 2 + 0 Der Rest ist 0 . Der letzte Rest davor war 2 : text{ggT}(42, 22) = 2 Bestimme text{ggT}(1071, 462) . 1071 = 2 cdot 462 + 147 qquad (2 cdot 462 = 924, 1071 - 924 = 147) 462 = 3 cdot 147 + mathbf{21} qquad (3 cdot 147 = 441, 462 - 441 = 21) 147 = 7 cdot 21 + 0 text{ggT}(1071, 462) = 21 Probe: 1071 : 21 = 51 und 462 : 21 = 22 ✓ – nur drei Zeilen statt langer Teilerlisten. Fliesen im Bad Ein Badboden ist 360 text{ cm} lang und 84 text{ cm} breit. Er soll ohne Schneiden mit möglichst großen quadratischen Fliesen ausgelegt werden. Wie groß sind die Fliesen, und wie vie
Worum geht's?
Formel mit Erklärung
- 1Große Zahl durch kleine Zahl teilen, mit Rest: a = q · b + r
- 2Neue Zeile: Die kleine Zahl wird zur großen, der Rest zur kleinen.
- 3Wiederholen, bis der Rest 0 ist.
- 4Der ggT ist der letzte Rest, der nicht 0 ist (der Divisor in der letzten Zeile).
Beispiele
Zusammenfassung
Jetzt üben
Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff:
