Euklidischer Algorithmus

Der euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Mit ihm lässt sich der größte gemeinsame Teiler zweier natürlicher Zahlen berechnen. Das Verfahren ist nach dem griechischen Mathematiker Euklid benannt, der es in seinem Werk „Die Elemente“ beschrieben hat.

Der größte gemeinsame Teiler zweier Zahlen kann auch aus ihren Primfaktorzerlegungen ermittelt werden. Ist aber von keiner der beiden Zahlen die Primfaktorzerlegung bekannt, so ist der euklidische Algorithmus das schnellste Verfahren zur Berechnung des größten gemeinsamen Teilers.

Der euklidische Algorithmus lässt sich nicht nur auf natürliche Zahlen anwenden. Vielmehr kann damit der größte gemeinsame Teiler von zwei Elementen eines jeden euklidischen Rings berechnet werden. Dazu zählen beispielsweise Polynome über einem Körper.