Editing Euclidean algorithm (section)

{{Short description|Algorithm for computing greatest common divisors}}
{{About|an algorithm for the greatest common divisor|the mathematics of space|Euclidean geometry|other uses of "Euclidean"|Euclidean (disambiguation)}}
{{Distinguish|Euclidean division}}
{{Featured article}}

<!-- FOR REASONS OF ACCESSIBILITY TO VISUALLY-IMPAIRED READERS (see [[WP:ACCESS]]), THIS ARTICLE AVOIDS <math> (i.e. LaTeX) MODE, UNLESS IT IS NECESSARY. PLEASE DO NOT ADD <math>-MODE FORMULAE, UNLESS YOU ALSO ADD THE CORRESPONDING ALT TEXT AS WELL, E.G., <math alt="description">. EXAMPLES CAN BE FOUND BELOW, E.G., IN THE "Matrix method" SECTION. -->
[[File: Euclid's algorithm Book VII Proposition 2 3.svg|upright=1.2|thumb|right|Euclid's method for finding the greatest common divisor (GCD) of two starting lengths BA and DC, both defined to be multiples of a common "unit" length. The length DC being shorter, it is used to "measure" BA, but only once because the remainder EA is less than DC. EA now measures (twice) the shorter length DC, with remainder FC shorter than EA. Then FC measures (three times) length EA. Because there is no remainder, the process ends with FC being the GCD. On the right [[Nicomachus]]'s example with numbers 49 and 21 resulting in their GCD of 7 (derived from Heath 1908:300).]]

In [[mathematics]], the '''Euclidean algorithm''',<ref group=note>Some widely used textbooks, such as [[I. N. Herstein]]'s ''Topics in Algebra'' and [[Serge Lang]]'s ''Algebra'', use the term "Euclidean algorithm" to refer to [[Euclidean division]]</ref> or '''Euclid's algorithm''', is an efficient method for computing the [[greatest common divisor]] (GCD) of two [[integers]], the largest number that divides them both without a [[remainder]]. It is named after the ancient Greek [[mathematician]] [[Euclid]], who first described it in [[Euclid's Elements|his ''Elements'']] ({{circa|300 BC}}).
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 [[Fraction (mathematics)|fraction]]s to their [[Irreducible fraction|simplest form]], and is a part of many other number-theoretic and cryptographic calculations.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, {{math|21}} is the GCD of {{math|252}} and {{math|105}} (as {{math|252 {{=}} 21 × 12}} and {{math|105 {{=}} 21 × 5)}}, and the same number {{math|21}} is also the GCD of {{math|105}} and {{math|252 − 105 {{=}} 147}}. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, that number is the GCD of the original two numbers. By [[#Bézout's identity|reversing the steps]] or using the [[extended Euclidean algorithm]], the GCD can be expressed as a [[linear combination]] of the two original numbers, that is the sum of the two numbers, each multiplied by an [[integer]] (for example, {{math|21 {{=}} 5 × 105 + (−2) × 252}}). The fact that the GCD can always be expressed in this way is known as [[Bézout's identity]].

The version of the Euclidean algorithm described above—which follows Euclid's original presentation—may require many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by [[Gabriel Lamé]] in 1844 ([[Lamé’s Theorem|Lamé's Theorem]]),<ref>{{cite journal |last=Lamé |first=Gabriel |year=1844 |title=Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers |journal=Comptes Rendus des Séances de l'Académie des Sciences |language=French |volume=19 |pages=867–870}}</ref><ref>{{cite journal |last=Shallit |first=Jeffrey |date=1994-11-01 |title=Origins of the analysis of the Euclidean algorithm |journal=Historia Mathematica |language=en |volume=21 |issue=4 |pages=401–419 |doi=10.1006/hmat.1994.1031 |issn=0315-0860|doi-access=free }}</ref> and marks the beginning of [[computational complexity theory]]. Additional methods for improving the algorithm's efficiency were developed in the 20th century.

The Euclidean algorithm has many theoretical and practical applications. It is used for reducing [[Fraction (mathematics)|fraction]]s to their [[Irreducible fraction|simplest form]] and for performing [[Division (mathematics)|division]] in [[modular arithmetic]]. Computations using this algorithm form part of the [[cryptographic protocol]]s that are used to secure [[internet]] communications, and in methods for breaking these cryptosystems by [[integer factorization|factoring large composite numbers]]. The Euclidean algorithm may be used to solve [[Diophantine equation]]s, such as finding numbers that satisfy multiple congruences according to the [[Chinese remainder theorem]], to construct [[simple continued fraction|continued fraction]]s, and to find accurate [[Diophantine approximation|rational approximations]] to real numbers. Finally, it can be used as a basic tool for proving theorems in [[number theory]] such as [[Lagrange's four-square theorem]] and the [[fundamental theorem of arithmetic|uniqueness of prime factorizations]].

The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as [[Gaussian integer]]s and [[polynomial]]s of one variable. This led to modern [[abstract algebra]]ic notions such as [[Euclidean domain]]s.