Euklidischer Algorithmus
Der euklidische Algorithmus ist ein Algorithmus aus der Zahlentheorie. Er erlaubt das effiziente Berechnen des größten gemeinsamen Teilers zweier Zahlen. Euklid beschrieb diesen Algorithmus in Buch VII seiner Elemente um das Jahr 300 v.Chr. Definition Für a, b ∈ ℕ ist ggT(a, b) der größte gemeinsame Teiler, d.h. die größte natürliche Zahl, die sowohl Teiler…
Weiterlesen