Algorithmus, euklidischer

größten gemeinsamen Teiler, kleinste gemeinsame Vielfache, teilerfremd

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.