Euclidean algorithm
Algoritmo de Euclides para el máximo común divisor
- Date
- c. 300 BCE · confidence medium
- Place
- Alexandria, Egypt
- Credited to
- Euclid (Elements, VII.1-2)
- People
- 👤 Euclides333 BCE–285 BCE
- Field
- Knowledge & symbols
What was discovered
Procedure using successive subtractions or divisions that finds the greatest common divisor of two numbers. It is the oldest non-trivial algorithm still in use.
Probably predates Euclid; Aristotle alludes to the antenaresis process.
What it led to
- continued fractions
- Bézout's identity
- modular arithmetic
- algorithm theory
Built on
- Pythagorean anthyphairesis