Euklidischer Algorithmus
Der euklidische Algorithmus ist eine effiziente Methode, um den größten gemeinsamen Teiler (ggT) von zwei Zahlen zu bestimmen. Der Algorithmus basiert auf dem Prinzip, dass der ggT von zwei Zahlen auch der ggT von der kleineren Zahl und dem Rest der Division der größeren durch die kleinere Zahl ist.
Algorithmus
- Teile die größere Zahl durch die kleinere und merke dir den Rest.
- Ersetze die größere Zahl durch die kleinere und die kleinere Zahl durch den Rest.
- Wiederhole Schritt 1 und 2, bis der Rest 0 ist.
- Der ggT ist die letzte Nicht-Null-Restzahl.
Beispielrechnung:
Bestimmen Sie den ggT von 56 und 98:
- 98 geteilt durch 56 ergibt einen Rest von 42.
- Ersetzen Sie 98 durch 56 und 56 durch 42 und wiederholen Sie Schritt 1.
- 56 geteilt durch 42 ergibt einen Rest von 14.
- Ersetzen Sie 56 durch 42 und 42 durch 14 und wiederholen Sie Schritt 1.
- 42 geteilt durch 14 ergibt einen Rest von 0, daher ist der ggT von 56 und 98 gleich 14.
Das Ergebnis zeigt, dass der größte gemeinsame Teiler von 56 und 98 tatsächlich 14 ist.