Embedded Files
Einführung
Einführung
Der Euklidische Algorithmus ist ein antikes, aber hocheffizientes Verfahren, um den größten gemeinsamen Teiler (ggT) zweier natürlicher Zahlen zu bestimmen.
Die Grundidee ist simpel: Der ggT von zwei Zahlen ändert sich nicht, wenn man die kleinere Zahl von der größeren abzieht. In der modernen Version nutzt man dafür die Division mit Rest (Modulo), da dies deutlich schneller zum Ziel führt.
Man teilt die größere Zahl durch die kleinere und schaut sich den Rest an. Dann ersetzt man die größere Zahl durch die kleinere und die kleinere durch den Rest. Das macht man so lange, bis der Rest 0 ist.
Der letzte Rest vor der Null ist dein ggT
Beispiel
Beispiel
Ein konkretes Beispiel: ggT von 252 und 105
Ein konkretes Beispiel: ggT von 252 und 105
Wir führen die Division mit Rest durch:
252 ÷ 105 = 2, Rest 42
(Rechnung: 252 = 2 *105 + 42)Jetzt nehmen wir die 105 und die 42:
105 ÷ 42 = 2, Rest 21
(Rechnung: 105 = 2 * 42 + 21)Jetzt nehmen wir die 42 und die 21:
42 ÷ 21 = 2, Rest 0
(Rechnung: 42 = 2 * 21 + 0)
Ergebnis: Der letzte Rest ungleich Null war die 21.
Also ist der ggT(252, 105) = 21.
Page updated
Google Sites
Report abuse