Algoritmo de Euclides para el máximo común divisor
Euclidean algorithm
- Fecha
- c. 300 a.C. · fiabilidad media
- Lugar
- Alejandría, Egipto
- Autoría
- Euclides (Elementos, VII.1-2)
- Personas
- 👤 Euclides333 a.C.–285 a.C.
- Ámbito
- Saber y símbolos
Qué se descubrió
Procedimiento por sustracciones o divisiones sucesivas que halla el máximo común divisor de dos números. Es el algoritmo no trivial más antiguo aún en uso.
Probablemente anterior a Euclides; Aristóteles alude a la antifairesis.
A qué dio paso
- fracciones continuas
- identidad de Bézout
- aritmética modular
- teoría de algoritmos
Se apoya en
- antifairesis de la escuela pitagórica