Euklidischer Algorithmus
Der sogenannte euklidische Algorithmus ist ein Verfahren zum Ermitteln des größten gemeinsamen Teilers (ggT) zweier Zahlen.
Beim euklidischen Algorithmus wird wie folgt verfahren:
Man teilt die größere durch die kleinere Zahl. Geht die Division auf, ist der Divisor der ggT. Geht die Division nicht auf, bleibt ein Rest. Dieser Rest ist der neue Divisor. Der alte Divisor wird zum Dividenden. Nun setzt man das Verfahren fort.
Nach endlich vielen Schritten erhält man den ggT.
Der sogenannte euklidische Algorithmus ist ein Verfahren zum Ermitteln des größten gemeinsamen Teilers (ggT) zweier Zahlen.
Da das kleinste gemeinsame Vielfache (kgV) zweier Zahlen der Quotient aus ihrem Produkt und ihrem ggT ist, lässt sich mit ihm auch das kgV ermitteln.
Beim euklidischer Algorithmus wird wie folgt verfahren:
Man teilt die größere durch die kleinere Zahl.
Geht die Division auf, ist der Divisor der ggT.
Geht die Division nicht auf, bleibt ein Rest. Dieser Rest ist der neue Divisor. Der alte Divisor wird zum Dividenden. Nun setzt man das Verfahren fort.
Nach endlich vielen Schritten erhält man den ggT.
In manchen Fällen ist dies die Zahl 1, dann sind die Ausgangszahlen teilerfremd.
Es ist der ggT von 544 und 391 gesucht.
| 544 | : | 391 = 1; | Rest 153 |
| 391 | : | 153 = 2; | Rest 85 |
| 153 | : | 85 = 1; | Rest 68 |
| 85 | : | 68 = 1; | Rest 17 |
| 68 | : | 17 = 4; | Rest 0 |
Die Divison geht auf, der ggT von 544 und 391 ist 17.
Daraus folgt: Das kgV von 544 und 391 ist
Es ist der ggT von 13 und 7 gesucht.
| 13 | : | 7 = 1; | Rest 6 |
| 7 | : | 6 = 1; | Rest 1 |
| 6 | : | 1 = 6; | Rest 0 |
Die Division geht auf, der ggT von 13 und 7 ist 1, d. h., 13 und 7 sind teilerfremd.
Daraus folgt: Das kgV von 13 und 7 ist das Produkt
