In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements .
It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules,
and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.
The Euclidean algorithm was probably invented before Euclid, depicted here holding a compass in a painting of about 1474.
Euclid was an ancient Greek mathematician active as a geometer and logician. Considered the "father of geometry", he is chiefly known for the Elements treatise, which established the foundations of geometry that largely dominated the field until the early 19th century. His system, now referred to as Euclidean geometry, involved new innovations in combination with a synthesis of theories from earlier Greek mathematicians, including Eudoxus of Cnidus, Hippocrates of Chios, Thales and Theaetetus. With Archimedes and Apollonius of Perga, Euclid is generally considered among the greatest mathematicians of antiquity, and one of the most influential in the history of mathematics.
Euclid by Jusepe de Ribera, c. 1630–1635
Detail of Raphael's impression of Euclid, teaching students in The School of Athens (1509–1511)
Domenico Maroli's 1650s painting Euclide di Megara si traveste da donna per recarsi ad Atene a seguire le lezioni di Socrate [Euclid of Megara Dressing as a Woman to Hear Socrates Teach in Athens]. At the time, Euclid the philosopher and Euclid the mathematician were wrongly considered the same person, so this painting includes mathematical objects on the table.
A papyrus fragment of Euclid's Elements dated to c. 75–125 AD. Found at Oxyrhynchus, the diagram accompanies Book II, Proposition 5.