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?

Wie findet man den ggT von 1071 1071 1071 und 462 462 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 × 22 42 \times 22 42 × 22 soll mit möglichst großen, gleichen Quadraten ausgelegt werden. Wir schneiden immer das größte Quadrat ab, das noch passt:
22 × 2220 × 2010 Quadrate 2 × 2
42 × 22: erst ein 22er-Quadrat, dann ein 20er-Quadrat, der Streifen 20 × 2 zerfällt in 2er-Quadrate
Am Ende geht alles glatt mit Quadraten der Seite 2 2 2 auf – und 2 2 2 ist genau ggT ( 42 , 22 ) \text{ggT}(42, 22) ggT ( 42 , 22 ) .

Formel mit Erklärung

Grundgedanke Ein gemeinsamer Teiler von a a a und b b b teilt auch den Rest von a : b a: b a : b . Deshalb gilt: ggT ( a , b ) = ggT ( b , r ) ( r = Rest von  a : b ) \text{ggT}(a, b) = \text{ggT}(b, r) \qquad (r = \text{Rest von } a: b) ggT ( a , b ) = ggT ( b , r ) ( r = Rest von  a : b ) Die Zahlen werden so immer kleiner, bis es aufgeht.
Euklidischer Algorithmus
  1. 1
    Große Zahl durch kleine Zahl teilen, mit Rest: a = q · b + r
  2. 2
    Neue Zeile: Die kleine Zahl wird zur großen, der Rest zur kleinen.
  3. 3
    Wiederholen, bis der Rest 0 ist.
  4. 4
    Der ggT ist der letzte Rest, der nicht 0 ist (der Divisor in der letzten Zeile).
Jede Zeile ist eine Division mit Rest in der Form a = q ⋅ b + r a = q \cdot b + r a = q ⋅ b + r .

Beispiele

Leicht#1
Bestimme ggT ( 42 , 22 ) \text{ggT}(42, 22) ggT ( 42 , 22 ) . 42 = 1 ⋅ 22 + 20 42 = 1 \cdot 22 + 20 42 = 1 ⋅ 22 + 20 22 = 1 ⋅ 20 + 2 22 = 1 \cdot 20 + \mathbf{2} 22 = 1 ⋅ 20 + 2 20 = 10 ⋅ 2 + 0 20 = 10 \cdot 2 + 0 20 = 10 ⋅ 2 + 0 Der Rest ist 0 0 0 . Der letzte Rest davor war 2 2 2 : ggT ( 42 , 22 ) = 2 \text{ggT}(42, 22) = 2 ggT ( 42 , 22 ) = 2

Zusammenfassung

Der euklidische Algorithmus berechnet den ggT durch wiederholte Division mit Rest. Idee: ggT ( a , b ) = ggT ( b , r ) \text{ggT}(a, b) = \text{ggT}(b, r) ggT ( a , b ) = ggT ( b , r ) – die Zahlen werden immer kleiner. Schema: a = q ⋅ b + r a = q \cdot b + r a = q ⋅ b + r , dann b b b und r r r weiterverwenden, bis der Rest 0 0 0 ist. Der letzte Rest ungleich 0 ist der ggT. Grundlage für den erweiterten euklidischen Algorithmus .

Jetzt üben

Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff: