HOME

TheInfoList




In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and
Serge Lang Serge Lang (; May 19, 1927 – September 12, 2005) was a French-American mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics a ...

Serge Lang
's ''Algebra'', use the term "Euclidean algorithm" to refer to
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of division (mathematics), dividing one integer (the dividend) by another (the divisor), in a way that produces a quotient and a remainder smaller than the divisor ...
or Euclid's algorithm, is an efficient method for computing the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...

greatest common divisor
(GCD) of two integers (numbers), the largest number that divides them both without a
remainder In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
. It is named after the ancient Greek
mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces ...

mathematician
Euclid Euclid (; grc-gre, Εὐκλείδης Euclid (; grc, Εὐκλείδης – ''Eukleídēs'', ; fl. 300 BC), sometimes called Euclid of Alexandria to distinguish him from Euclid of Megara, was a Greek mathematician, often referre ...

Euclid
, who first described it in his ''Elements'' (c. 300 BC). It is an example of an ''
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

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 A fraction (from Latin ', "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight-fifths ...
s to their 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, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 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, they are the GCD of the original two numbers. By reversing the steps or using the
extended Euclidean algorithm In arithmetic Arithmetic (from the Ancient Greek, Greek wikt:en:ἀριθμός#Ancient Greek, ἀριθμός ''arithmos'', 'number' and wikt:en:τική#Ancient Greek, τική wikt:en:τέχνη#Ancient Greek, έχνη ''tiké échne', 'art' ...
, the GCD can be expressed as a
linear combination In mathematics, a linear combination is an Expression (mathematics), expression constructed from a Set (mathematics), set of terms by multiplying each term by a constant and adding the results (e.g. a linear combination of ''x'' and ''y'' would be ...
of the two original numbers, that is the sum of the two numbers, each multiplied by an
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
(for example, 21 = 5 × 105 + (−2) × 252). The fact that the GCD can always be expressed in this way is known as
Bézout's identity In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical ...
. The version of the Euclidean algorithm described above (and by Euclid) can take 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é Gabriel Lamé (22 July 1795 – 1 May 1870) was a French mathematician who contributed to the theory of partial differential equation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity ( ...

Gabriel Lamé
in 1844, and marks the beginning of
computational complexity theory Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by ...
. 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 A fraction (from Latin ', "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight-fifths ...
s to their simplest form and for performing
division Division or divider may refer to: Mathematics *Division (mathematics), the inverse of multiplication *Division algorithm, a method for computing the result of mathematical division Military *Division (military), a formation typically consisting ...
in
modular arithmetic #REDIRECT Modular arithmetic #REDIRECT Modular arithmetic#REDIRECT Modular arithmetic In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure ( ...
. Computations using this algorithm form part of the
cryptographic protocol A security protocol (cryptographic protocol or encryption protocol) is an abstract or concrete protocol Protocol may refer to: Sociology and politics * Protocol (politics) Protocol originally (in Late Middle English, c. 15th century) meant the mi ...
s that are used to secure
internet The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a ''internetworking, network of networks'' that consist ...

internet
communications, and in methods for breaking these cryptosystems by factoring large composite numbers. The Euclidean algorithm may be used to solve
Diophantine equation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
s, such as finding numbers that satisfy multiple congruences according to the
Chinese remainder theorem In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of the ...
, to construct
continued fraction In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
s, and to find accurate rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen ...

number theory
such as
Lagrange's four-square theorem Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer square number, squares. That is, the squares form an additive basis of order four. :p = a_0^2 + a_ ...
and the 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 In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as . This inte ...
s and
polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

polynomial
s of one variable. This led to modern
abstract algebra In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathema ...
ic notions such as
Euclidean domain In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a #Definition, Euclidean function which allows a suitable generalization of the Euclidean division of ...
s.


Background: greatest common divisor

The Euclidean algorithm calculates the greatest common divisor (GCD) of two
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
s ''a'' and ''b''. The greatest common divisor ''g'' is the largest natural number that divides both ''a'' and ''b'' without leaving a remainder. Synonyms for the GCD include the ''greatest common factor'' (GCF), the ''highest common factor'' (HCF), the ''highest common divisor'' (HCD), and the ''greatest common measure'' (GCM). The greatest common divisor is often written as gcd(''a'', ''b'') or, more simply, as (''a'', ''b''), although the latter notation is ambiguous, also used for concepts such as an
ideal Ideal may refer to: Philosophy * Ideal (ethics) An ideal is a principle A principle is a proposition or value that is a guide for behavior or evaluation. In law Law is a system A system is a group of Interaction, interacting ...
in the
ring of integers In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
, which is closely related to GCD. If gcd(''a'', ''b'') = 1, then ''a'' and ''b'' are said to be
coprime In number theory, two integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "whole") is colloquially defined as a number that can be written without a Fraction (mathematics), fractional component. For example, 21, 4, 0, ...
(or relatively prime). This property does not imply that ''a'' or ''b'' are themselves
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s. For example, neither 6 nor 35 is a prime number, since they both have two prime factors: 6 = 2 × 3 and 35 = 5 × 7. Nevertheless, 6 and 35 are coprime. No natural number other than 1 divides both 6 and 35, since they have no prime factors in common. Let ''g'' = gcd(''a'', ''b''). Since ''a'' and ''b'' are both multiples of ''g'', they can be written ''a'' = ''mg'' and ''b'' = ''ng'', and there is no larger number ''G'' > ''g'' for which this is true. The natural numbers ''m'' and ''n'' must be coprime, since any common factor could be factored out of ''m'' and ''n'' to make ''g'' greater. Thus, any other number ''c'' that divides both ''a'' and ''b'' must also divide ''g''. The greatest common divisor ''g'' of ''a'' and ''b'' is the unique (positive) common divisor of ''a'' and ''b'' that is divisible by any other common divisor ''c''. The GCD can be visualized as follows. Consider a rectangular area ''a'' by ''b'', and any common divisor ''c'' that divides both ''a'' and ''b'' exactly. The sides of the rectangle can be divided into segments of length ''c'', which divides the rectangle into a grid of squares of side length ''c''. The greatest common divisor ''g'' is the largest value of ''c'' for which this is possible. For illustration, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, 6-by-6 squares or 12-by-12 squares. Therefore, 12 is the greatest common divisor of 24 and 60. A 24-by-60 rectangular area can be divided into a grid of 12-by-12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5). The GCD of two numbers ''a'' and ''b'' is the product of the prime factors shared by the two numbers, where a same prime factor can be used multiple times, but only as long as the product of these factors divides both ''a'' and ''b''. For example, since 1386 can be factored into 2 × 3 × 3 × 7 × 11, and 3213 can be factored into 3 × 3 × 3 × 7 × 17, the greatest common divisor of 1386 and 3213 equals 63 = 3 × 3 × 7, the product of their shared prime factors. If two numbers have no prime factors in common, their greatest common divisor is 1 (obtained here as an instance of the
empty product In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
), in other words they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors.
Factorization In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
of large integers is believed to be a computationally very difficult problem, and the security of many widely used
cryptographic protocol A security protocol (cryptographic protocol or encryption protocol) is an abstract or concrete protocol Protocol may refer to: Sociology and politics * Protocol (politics) Protocol originally (in Late Middle English, c. 15th century) meant the mi ...
s is based upon its infeasibility. Another definition of the GCD is helpful in advanced mathematics, particularly
ring theory In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. ...
. The greatest common divisor ''g''  of two nonzero numbers ''a'' and ''b'' is also their smallest positive integral linear combination, that is, the smallest positive number of the form ''ua'' + ''vb'' where ''u'' and ''v'' are integers. The set of all integral linear combinations of ''a'' and ''b'' is actually the same as the set of all multiples of ''g'' (''mg'', where ''m'' is an integer). In modern mathematical language, the
ideal Ideal may refer to: Philosophy * Ideal (ethics) An ideal is a principle A principle is a proposition or value that is a guide for behavior or evaluation. In law Law is a system A system is a group of Interaction, interacting ...
generated by ''a'' and ''b'' is the ideal generated by ''g'' alone (an ideal generated by a single element is called a
principal ideal In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
, and all ideals of the integers are principal ideals). Some properties of the GCD are in fact easier to see with this description, for instance the fact that any common divisor of ''a'' and ''b'' also divides the GCD (it divides both terms of ''ua'' + ''vb''). The equivalence of this GCD definition with the other definitions is described below. The GCD of three or more numbers equals the product of the prime factors common to all the numbers, but it can also be calculated by repeatedly taking the GCDs of pairs of numbers. For example, : Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers.


Description


Procedure

The Euclidean algorithm proceeds in a series of steps such that the output of each step is used as an input for the next one. Let ''k'' be an integer that counts the steps of the algorithm, starting with zero. Thus, the initial step corresponds to ''k'' = 0, the next step corresponds to ''k'' = 1, and so on. Each step begins with two nonnegative remainders ''r''''k''−1 and ''r''''k''−2. Since the algorithm ensures that the remainders decrease steadily with every step, ''r''''k''−1 is less than its predecessor ''r''''k''−2. The goal of the ''k''th step is to find a
quotient In arithmetic Arithmetic (from the Ancient Greek, Greek wikt:en:ἀριθμός#Ancient Greek, ἀριθμός ''arithmos'', 'number' and wikt:en:τική#Ancient Greek, τική wikt:en:τέχνη#Ancient Greek, έχνη ''tiké échne' ...
''q''''k'' and
remainder In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
''r''''k'' that satisfy the equation :r_ = q_k r_ + r_k and that have 0 ≤ ''r''''k'' < ''r''''k''−1. In other words, multiples of the smaller number ''r''''k''−1 are subtracted from the larger number ''r''''k''−2 until the remainder ''r''''k'' is smaller than ''r''''k''−1. In the initial step (''k'' = 0), the remainders ''r''−2 and ''r''−1 equal ''a'' and ''b'', the numbers for which the GCD is sought. In the next step (''k'' = 1), the remainders equal ''b'' and the remainder ''r''0 of the initial step, and so on. Thus, the algorithm can be written as a sequence of equations :\begin a &= q_0 b + r_0 \\ b &= q_1 r_0 + r_1 \\ r_0 &= q_2 r_1 + r_2 \\ r_1 &=q_3 r_2 + r_3 \\ &\,\,\,\vdots \end If ''a'' is smaller than ''b'', the first step of the algorithm swaps the numbers. For example, if ''a'' < ''b'', the initial quotient ''q''0 equals zero, and the remainder ''r''0 is ''a''. Thus, ''r''''k'' is smaller than its predecessor ''r''''k''−1 for all ''k'' ≥ 0. Since the remainders decrease with every step but can never be negative, a remainder ''r''''N'' must eventually equal zero, at which point the algorithm stops. The final nonzero remainder ''r''''N''−1 is the greatest common divisor of ''a'' and ''b''. The number ''N'' cannot be infinite because there are only a finite number of nonnegative integers between the initial remainder ''r''0 and zero.


Proof of validity

The validity of the Euclidean algorithm can be proven by a two-step argument. In the first step, the final nonzero remainder ''r''''N''−1 is shown to divide both ''a'' and ''b''. Since it is a common divisor, it must be less than or equal to the greatest common divisor ''g''. In the second step, it is shown that any common divisor of ''a'' and ''b'', including ''g'', must divide ''r''''N''−1; therefore, ''g'' must be less than or equal to ''r''''N''−1. These two conclusions are inconsistent unless ''r''''N''−1 = ''g''. To demonstrate that ''r''''N''−1 divides both ''a'' and ''b'' (the first step), ''r''''N''−1 divides its predecessor ''r''''N''−2 : since the final remainder ''r''''N'' is zero. ''r''''N''−1 also divides its next predecessor ''r''''N''−3 : because it divides both terms on the right-hand side of the equation. Iterating the same argument, ''r''''N''−1 divides all the preceding remainders, including ''a'' and ''b''. None of the preceding remainders ''r''''N''−2, ''r''''N''−3, etc. divide ''a'' and ''b'', since they leave a remainder. Since ''r''''N''−1 is a common divisor of ''a'' and ''b'', ''r''''N''−1 ≤ ''g''. In the second step, any natural number ''c'' that divides both ''a'' and ''b'' (in other words, any common divisor of ''a'' and ''b'') divides the remainders ''r''''k''. By definition, ''a'' and ''b'' can be written as multiples of ''c'' : ''a'' = ''mc'' and ''b'' = ''nc'', where ''m'' and ''n'' are natural numbers. Therefore, ''c'' divides the initial remainder ''r''0, since ''r''0 = ''a'' − ''q''0''b'' = ''mc'' − ''q''0''nc'' = (''m'' − ''q''0''n'')''c''. An analogous argument shows that ''c'' also divides the subsequent remainders ''r''1, ''r''2, etc. Therefore, the greatest common divisor ''g'' must divide ''r''''N''−1, which implies that ''g'' ≤ ''r''''N''−1. Since the first part of the argument showed the reverse (''r''''N''−1 ≤ ''g''), it follows that ''g'' = ''r''''N''−1. Thus, ''g'' is the greatest common divisor of all the succeeding pairs: :


Worked example

For illustration, the Euclidean algorithm can be used to find the greatest common divisor of ''a'' = 1071 and ''b'' = 462. To begin, multiples of 462 are subtracted from 1071 until the remainder is less than 462. Two such multiples can be subtracted (''q''0 = 2), leaving a remainder of 147: : Then multiples of 147 are subtracted from 462 until the remainder is less than 147. Three multiples can be subtracted (''q''1 = 3), leaving a remainder of 21: : Then multiples of 21 are subtracted from 147 until the remainder is less than 21. Seven multiples can be subtracted (''q''2 = 7), leaving no remainder: : Since the last remainder is zero, the algorithm ends with 21 as the greatest common divisor of 1071 and 462. This agrees with the gcd(1071, 462) found by prime factorization above. In tabular form, the steps are:


Visualization

The Euclidean algorithm can be visualized in terms of the tiling analogy given above for the greatest common divisor. Assume that we wish to cover an ''a''-by-''b'' rectangle with square tiles exactly, where ''a'' is the larger of the two numbers. We first attempt to tile the rectangle using ''b''-by-''b'' square tiles; however, this leaves an ''r''0-by-''b'' residual rectangle untiled, where ''r''0 < ''b''. We then attempt to tile the residual rectangle with ''r''0-by-''r''0 square tiles. This leaves a second residual rectangle ''r''1-by-''r''0, which we attempt to tile using ''r''1-by-''r''1 square tiles, and so on. The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the previous residual rectangle exactly. The length of the sides of the smallest square tile is the GCD of the dimensions of the original rectangle. For example, the smallest square tile in the adjacent figure is 21-by-21 (shown in red), and 21 is the GCD of 1071 and 462, the dimensions of the original rectangle (shown in green).


Euclidean division

At every step ''k'', the Euclidean algorithm computes a quotient ''q''''k'' and remainder ''r''''k'' from two numbers ''r''''k''−1 and ''r''''k''−2 : where the ''r''''k'' is non-negative and is strictly less than the
absolute value In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...

absolute value
of ''r''''k''−1. The theorem which underlies the definition of the
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of division (mathematics), dividing one integer (the dividend) by another (the divisor), in a way that produces a quotient and a remainder smaller than the divisor ...
ensures that such a quotient and remainder always exist and are unique. In Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is, ''r''''k''−1 is subtracted from ''r''''k''−2 repeatedly until the remainder ''r''''k'' is smaller than ''r''''k''−1. After that ''r''''k'' and ''r''''k''−1 are exchanged and the process is iterated. Euclidean division reduces all the steps between two exchanges into a single step, which is thus more efficient. Moreover, the quotients are not needed, thus one may replace Euclidean division by the
modulo operation In computing, the modulo operation returns the remainder or signed remainder of a Division (mathematics), division, after one number is divided by another (called the ''modular arithmetic, modulus'' of the operation). Given two positive numbers a ...
, which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply :


Implementations

Implementations of the algorithm may be expressed in
pseudocode In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
. For example, the division-based version may be programmed as function gcd(a, b) while b ≠ 0 t := b b := a mod b a := t return a At the beginning of the ''k''th iteration, the variable ''b'' holds the latest remainder ''r''''k''−1, whereas the variable ''a'' holds its predecessor, ''r''''k''−2. The step ''b'' := ''a'' mod ''b'' is equivalent to the above recursion formula ''r''''k'' ≡ ''r''''k''−2 mod ''r''''k''−1. The
temporary variable In computer programming, a temporary variable is a variable (programming), variable with short object lifetime, lifetime, usually to hold data (computing), data that will soon be discarded, or before it can be placed at a more permanent memory loca ...
''t'' holds the value of ''r''''k''−1 while the next remainder ''r''''k'' is being calculated. At the end of the loop iteration, the variable ''b'' holds the remainder ''r''''k'', whereas the variable ''a'' holds its predecessor, ''r''''k''−1. (If negative inputs are allowed, or if the mod function may return negative values, the last line must be changed into return max(a, −a).) In the subtraction-based version, which was Euclid's original version, the remainder calculation (b := a mod b) is replaced by repeated subtraction. Contrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops when ''a'' = ''b'': function gcd(a, b) while a ≠ b if a > b a := a − b else b := b − a return a The variables ''a'' and ''b'' alternate holding the previous remainders ''r''''k''−1 and ''r''''k''−2. Assume that ''a'' is larger than ''b'' at the beginning of an iteration; then ''a'' equals ''r''''k''−2, since ''r''''k''−2 > ''r''''k''−1. During the loop iteration, ''a'' is reduced by multiples of the previous remainder ''b'' until ''a'' is smaller than ''b''. Then ''a'' is the next remainder ''r''''k''. Then ''b'' is reduced by multiples of ''a'' until it is again smaller than ''a'', giving the next remainder ''r''''k''+1, and so on. The recursive version is based on the equality of the GCDs of successive remainders and the stopping condition gcd(''r''''N''−1, 0) = ''r''''N''−1. function gcd(a, b) if b = 0 return a else return gcd(b, a mod b) (As above, if negative inputs are allowed, or if the mod function may return negative values, the instruction "return a" must be changed into "return max(a, −a)".) For illustration, the gcd(1071, 462) is calculated from the equivalent gcd(462, 1071 mod 462) = gcd(462, 147). The latter GCD is calculated from the gcd(147, 462 mod 147) = gcd(147, 21), which in turn is calculated from the gcd(21, 147 mod 21) = gcd(21, 0) = 21.


Method of least absolute remainders

In another version of Euclid's algorithm, the quotient at each step is increased by one if the resulting negative remainder is smaller in magnitude than the typical positive remainder. Previously, the equation : assumed that . However, an alternative negative remainder can be computed: : if or : if . If is replaced by when , then one gets a variant of Euclidean algorithm such that : at each step.
Leopold Kronecker Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a German German(s) may refer to: Common uses * of or related to Germany * Germans, Germanic ethnic group, citizens of Germany or people of German ancestry * For citizens of German ...

Leopold Kronecker
has shown that this version requires the fewest steps of any version of Euclid's algorithm. More generally, it has been proven that, for every input numbers ''a'' and ''b'', the number of steps is minimal if and only if is chosen in order that \left , \frac\right , <\frac\sim 0.618, where \varphi is the
golden ratio In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ...

golden ratio
.


Historical development

The Euclidean algorithm is one of the oldest algorithms in common use., p. 318 It appears in Euclid's ''Elements'' (c. 300 BC), specifically in Book 7 (Propositions 1–2) and Book 10 (Propositions 2–3). In Book 7, the algorithm is formulated for integers, whereas in Book 10, it is formulated for lengths of line segments. (In modern usage, one would say it was formulated there for
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s. But lengths, areas, and volumes, represented as real numbers in modern usage, are not measured in the same units and there is no natural unit of length, area, or volume; the concept of real numbers was unknown at that time.) The latter algorithm is geometrical. The GCD of two lengths ''a'' and ''b'' corresponds to the greatest length ''g'' that measures ''a'' and ''b'' evenly; in other words, the lengths ''a'' and ''b'' are both integer multiples of the length ''g''. The algorithm was probably not discovered by
Euclid Euclid (; grc-gre, Εὐκλείδης Euclid (; grc, Εὐκλείδης – ''Eukleídēs'', ; fl. 300 BC), sometimes called Euclid of Alexandria to distinguish him from Euclid of Megara, was a Greek mathematician, often referre ...

Euclid
, who compiled results from earlier mathematicians in his ''Elements''. The mathematician and historian B. L. van der Waerden suggests that Book VII derives from a textbook on
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen ...

number theory
written by mathematicians in the school of
Pythagoras Pythagoras of Samos, or simply ; in Ionian Greek () was an ancient Ionians, Ionian Ancient Greek philosophy, Greek philosopher and the eponymous founder of Pythagoreanism. His political and religious teachings were well known in Magna Graec ...

Pythagoras
. The algorithm was probably known by
Eudoxus of Cnidus Eudoxus of Cnidus (; grc, Εὔδοξος ὁ Κνίδιος, ''Eúdoxos ho Knídios''; ) was an ancient Greek Ancient Greek includes the forms of the Greek language used in ancient Greece and the classical antiquity, ancient world from ...
(about 375 BC). The algorithm may even pre-date Eudoxus, judging from the use of the technical term ἀνθυφαίρεσις (''anthyphairesis'', reciprocal subtraction) in works by Euclid and
Aristotle Aristotle (; grc-gre, Ἀριστοτέλης ''Aristotélēs'', ; 384–322 BC) was a Greek philosopher A philosopher is someone who practices philosophy Philosophy (from , ) is the study of general and fundamental questio ...

Aristotle
. Centuries later, Euclid's algorithm was discovered independently both in India and in China, primarily to solve
Diophantine equation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
s that arose in astronomy and making accurate calendars. In the late 5th century, the Indian mathematician and astronomer
Aryabhata Aryabhata (, ISO The International Organization for Standardization (ISO ) is an international standard An international standard is a technical standard A technical standard is an established norm (social), norm or requirement for a repe ...
described the algorithm as the "pulverizer", perhaps because of its effectiveness in solving Diophantine equations. Although a special case of the
Chinese remainder theorem In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of the ...
had already been described in the Chinese book ''
Sunzi Suanjing ''Sunzi Suanjing'' () was a mathematical treatise A treatise is a formal and systematic written discourse on some subject, generally longer and treating it in greater depth than an essay, and more concerned with investigating or exposing the p ...
'', the general solution was published by
Qin Jiushao Qin Jiushao (, ca. 1202–1261), courtesy name A courtesy name (), also known as a style name, is a name bestowed upon one at adulthood in addition to one's given name. This practice is a tradition in the Sinosphere, including China, Japan, Ko ...
in his 1247 book ''Shushu Jiuzhang'' (數書九章 '' Mathematical Treatise in Nine Sections''). The Euclidean algorithm was first described ''numerically'' and popularized in Europe in the second edition of Bachet's ''Problèmes plaisants et délectables'' (''Pleasant and enjoyable problems'', 1624). In Europe, it was likewise used to solve Diophantine equations and in developing
continued fraction In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
s. The
extended Euclidean algorithm In arithmetic Arithmetic (from the Ancient Greek, Greek wikt:en:ἀριθμός#Ancient Greek, ἀριθμός ''arithmos'', 'number' and wikt:en:τική#Ancient Greek, τική wikt:en:τέχνη#Ancient Greek, έχνη ''tiké échne', 'art' ...
was published by the English mathematician
Nicholas Saunderson Nicholas Saunderson (20 January 1682 – 19 April 1739) was a blind English scientist and mathematician. According to one historian of statistics, he may have been the earliest discoverer of Bayes' theorem. He worked as Lucasian Professor of ...
, who attributed it to
Roger Cotes Roger Cotes FRS FRS may also refer to: Government and politics * Facility Registry System, a centrally managed Environmental Protection Agency database that identifies places of environmental interest in the United States * Family Resources ...

Roger Cotes
as a method for computing continued fractions efficiently. In the 19th century, the Euclidean algorithm led to the development of new number systems, such as
Gaussian integer In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as . This inte ...
s and
Eisenstein integer In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
s. In 1815,
Carl Gauss Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a and physicist who made significant contributions to many fields in mathematics and science. Sometimes referred to as the ''Princ ...

Carl Gauss
used the Euclidean algorithm to demonstrate unique factorization of
Gaussian integer In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as . This inte ...
s, although his work was first published in 1832. Gauss mentioned the algorithm in his ''
Disquisitiones Arithmeticae The (Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to be in relation wit ...
'' (published 1801), but only as a method for
continued fraction In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
s.
Peter Gustav Lejeune Dirichlet Johann Peter Gustav Lejeune Dirichlet (; 13 February 1805 – 5 May 1859) was a German German(s) may refer to: Common uses * of or related to Germany * Germans, Germanic ethnic group, citizens of Germany or people of German ancestry * For c ...

Peter Gustav Lejeune Dirichlet
seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory. Lejeune Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied. Lejeune Dirichlet's lectures on number theory were edited and extended by
Richard Dedekind Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German German(s) may refer to: Common uses * of or related to Germany * Germans, Germanic ethnic group, citizens of Germany or people of German ancestry * For citiz ...
, who used Euclid's algorithm to study
algebraic integer In algebraic number theory Algebraic number theory is a branch of number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777 ...
s, a new general type of number. For example, Dedekind was the first to prove
Fermat's two-square theorem In additive number theory Additive number theory is the subfield of number theory concerning the study of subsets of integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "whole") is colloquially defined as a number that ...
using the unique factorization of Gaussian integers. Dedekind also defined the concept of a
Euclidean domain In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a #Definition, Euclidean function which allows a suitable generalization of the Euclidean division of ...
, a number system in which a generalized version of the Euclidean algorithm can be defined (as described
below Below may refer to: *Earth *Ground (disambiguation) *Soil *Floor *Bottom (disambiguation) *Less than *Temperatures below freezing *Hell or underworld People with the surname *Fred Below (1926–1988), American blues drummer *Fritz von Below (1853 ...
). In the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of
ideals Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring considered ...
. Other applications of Euclid's algorithm were developed in the 19th century. In 1829,
Charles Sturm Charles is a masculine given name predominantly found in English language, English and French language, French speaking countries. It is from the French form ''Charles'' of a Germanic name ''Karl''. The original Anglo-Saxon was ''Churl, Ċea ...
showed that the algorithm was useful in the
Sturm chain In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
method for counting the real roots of polynomials in any given interval. The Euclidean algorithm was the first
integer relation algorithmAn integer relation between a set of real numbers ''x''1, ''x''2, ..., ''x'n'' is a set of integers ''a''1, ''a''2, ..., ''a'n'', not all 0, such that :a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\, An integer relation algorithm is an algorithm ...
, which is a method for finding integer relations between commensurate real numbers. Several novel
integer relation algorithmAn integer relation between a set of real numbers ''x''1, ''x''2, ..., ''x'n'' is a set of integers ''a''1, ''a''2, ..., ''a'n'', not all 0, such that :a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\, An integer relation algorithm is an algorithm ...
s have been developed, such as the algorithm of
Helaman Ferguson Helaman Rolfe Pratt Ferguson (born 1940 in Salt Lake City Salt Lake City (often shortened to Salt Lake and abbreviated as SLC) is the Capital (political), capital and List of cities and towns in Utah, most populous city of the U.S. state of Uta ...
and R.W. Forcade (1979) and the LLL algorithm. In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called ''The Game of Euclid'', which has an optimal strategy. The players begin with two piles of ''a'' and ''b'' stones. The players take turns removing ''m'' multiples of the smaller pile from the larger. Thus, if the two piles consist of ''x'' and ''y'' stones, where ''x'' is larger than ''y'', the next player can reduce the larger pile from ''x'' stones to ''x'' − ''my'' stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.


Mathematical applications


Bézout's identity

Bézout's identity In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical ...
states that the greatest common divisor ''g'' of two integers ''a'' and ''b'' can be represented as a linear sum of the original two numbers ''a'' and ''b''. In other words, it is always possible to find integers ''s'' and ''t'' such that ''g'' = ''sa'' + ''tb''. The integers ''s'' and ''t'' can be calculated from the quotients ''q''0, ''q''1, etc. by reversing the order of equations in Euclid's algorithm. Beginning with the next-to-last equation, ''g'' can be expressed in terms of the quotient ''q''''N''−1 and the two preceding remainders, ''r''''N''−2 and ''r''''N''−3: : Those two remainders can be likewise expressed in terms of their quotients and preceding remainders, : and : Substituting these formulae for ''r''''N''−2 and ''r''''N''−3 into the first equation yields ''g'' as a linear sum of the remainders ''r''''N''−4 and ''r''''N''−5. The process of substituting remainders by formulae involving their predecessors can be continued until the original numbers ''a'' and ''b'' are reached: : : : After all the remainders ''r''0, ''r''1, etc. have been substituted, the final equation expresses ''g'' as a linear sum of ''a'' and ''b'': ''g'' = ''sa'' + ''tb''.
Bézout's identity In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical ...
, and therefore the previous algorithm, can both be generalized to the context of
Euclidean domain In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a #Definition, Euclidean function which allows a suitable generalization of the Euclidean division of ...
s.


Principal ideals and related problems

Bézout's identity provides yet another definition of the greatest common divisor ''g'' of two numbers ''a'' and ''b''. Consider the set of all numbers ''ua'' + ''vb'', where ''u'' and ''v'' are any two integers. Since ''a'' and ''b'' are both divisible by ''g'', every number in the set is divisible by ''g''. In other words, every number of the set is an integer multiple of ''g''. This is true for every common divisor of ''a'' and ''b''. However, unlike other common divisors, the greatest common divisor is a member of the set; by Bézout's identity, choosing ''u'' = ''s'' and ''v'' = ''t'' gives ''g''. A smaller common divisor cannot be a member of the set, since every member of the set must be divisible by ''g''. Conversely, any multiple ''m'' of ''g'' can be obtained by choosing ''u'' = ''ms'' and ''v'' = ''mt'', where ''s'' and ''t'' are the integers of Bézout's identity. This may be seen by multiplying Bézout's identity by ''m'', : Therefore, the set of all numbers ''ua'' + ''vb'' is equivalent to the set of multiples ''m'' of ''g''. In other words, the set of all possible sums of integer multiples of two numbers (''a'' and ''b'') is equivalent to the set of multiples of gcd(''a'', ''b''). The GCD is said to be the generator of the
ideal Ideal may refer to: Philosophy * Ideal (ethics) An ideal is a principle A principle is a proposition or value that is a guide for behavior or evaluation. In law Law is a system A system is a group of Interaction, interacting ...
of ''a'' and ''b''. This GCD definition led to the modern
abstract algebra In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathema ...
ic concepts of a
principal ideal In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
(an ideal generated by a single element) and a
principal ideal domain In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
(a
domain Domain may refer to: Mathematics *Domain of a function In mathematics, the domain of a Function (mathematics), function is the Set (mathematics), set of inputs accepted by the function. It is sometimes denoted by \operatorname(f), where is th ...
in which every ideal is a principal ideal). Certain problems can be solved using this result. For example, consider two measuring cups of volume ''a'' and ''b''. By adding/subtracting ''u'' multiples of the first cup and ''v'' multiples of the second cup, any volume ''ua'' + ''vb'' can be measured out. These volumes are all multiples of ''g'' = gcd(''a'', ''b'').


Extended Euclidean algorithm

The integers ''s'' and ''t'' of Bézout's identity can be computed efficiently using the
extended Euclidean algorithm In arithmetic Arithmetic (from the Ancient Greek, Greek wikt:en:ἀριθμός#Ancient Greek, ἀριθμός ''arithmos'', 'number' and wikt:en:τική#Ancient Greek, τική wikt:en:τέχνη#Ancient Greek, έχνη ''tiké échne', 'art' ...
. This extension adds two recursive equations to Euclid's algorithm : : with the starting values : : Using this recursion, Bézout's integers ''s'' and ''t'' are given by ''s'' = ''s''''N'' and ''t'' = ''t''''N'', where ''N+1'' is the step on which the algorithm terminates with ''r''''N+1'' = 0. The validity of this approach can be shown by induction. Assume that the recursion formula is correct up to step ''k'' − 1 of the algorithm; in other words, assume that : for all ''j'' less than ''k''. The ''k''th step of the algorithm gives the equation : Since the recursion formula has been assumed to be correct for ''r''''k''−2 and ''r''''k''−1, they may be expressed in terms of the corresponding ''s'' and ''t'' variables : Rearranging this equation yields the recursion formula for step ''k'', as required :


Matrix method

The integers ''s'' and ''t'' can also be found using an equivalent
matrix Matrix or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols, or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the material in between a eukaryot ...
method. The sequence of equations of Euclid's algorithm : \begin a & = q_0 b + r_0 \\ b & = q_1 r_0 + r_1 \\ & \,\,\,\vdots \\ r_ & = q_N r_ + 0 \end can be written as a product of 2-by-2 quotient matrices multiplying a two-dimensional remainder vector : \begin a \\ b \end = \begin q_0 & 1 \\ 1 & 0 \end \begin b \\ r_0 \end = \begin q_0 & 1 \\ 1 & 0 \end \begin q_1 & 1 \\ 1 & 0 \end \begin r_0 \\ r_1 \end = \cdots = \prod_^N \begin q_i & 1 \\ 1 & 0 \end \begin r_ \\ 0 \end \,. Let M represent the product of all the quotient matrices : \mathbf = \begin m_ & m_ \\ m_ & m_ \end = \prod_^N \begin q_i & 1 \\ 1 & 0 \end = \begin q_0 & 1 \\ 1 & 0 \end \begin q_1 & 1 \\ 1 & 0 \end \cdots \begin q_ & 1 \\ 1 & 0 \end \,. This simplifies the Euclidean algorithm to the form : \begin a \\ b \end = \mathbf \begin r_ \\ 0 \end = \mathbf \begin g \\ 0 \end \,. To express ''g'' as a linear sum of ''a'' and ''b'', both sides of this equation can be multiplied by the
inverse Inverse or invert may refer to: Science and mathematics * Inverse (logic), a type of conditional sentence which is an immediate inference made from another conditional sentence * Additive inverse (negation), the inverse of a number that, when add ...
of the matrix M. The
determinant In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

determinant
of M equals (−1)''N''+1, since it equals the product of the determinants of the quotient matrices, each of which is negative one. Since the determinant of M is never zero, the vector of the final remainders can be solved using the inverse of M : \begin g \\ 0 \end = \mathbf^ \begin a \\ b \end = (-1)^ \begin m_ & -m_ \\ -m_ & m_ \end \begin a \\ b \end \,. Since the top equation gives : the two integers of Bézout's identity are ''s'' = (−1)''N''+1''m''22 and ''t'' = (−1)''N''''m''12. The matrix method is as efficient as the equivalent recursion, with two multiplications and two additions per step of the Euclidean algorithm.


Euclid's lemma and unique factorization

Bézout's identity is essential to many applications of Euclid's algorithm, such as demonstrating the
unique factorization In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
of numbers into prime factors. To illustrate this, suppose that a number ''L'' can be written as a product of two factors ''u'' and ''v'', that is, ''L'' = ''uv''. If another number ''w'' also divides ''L'' but is coprime with ''u'', then ''w'' must divide ''v'', by the following argument: If the greatest common divisor of ''u'' and ''w'' is 1, then integers ''s'' and ''t'' can be found such that : by Bézout's identity. Multiplying both sides by ''v'' gives the relation : Since ''w'' divides both terms on the right-hand side, it must also divide the left-hand side, ''v''. This result is known as
Euclid's lemma In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. I ...
. Specifically, if a prime number divides ''L'', then it must divide at least one factor of ''L''. Conversely, if a number ''w'' is coprime to each of a series of numbers ''a''1, ''a''2, ..., ''a''''n'', then ''w'' is also coprime to their product, ''a''1 × ''a''2 × ... × ''a''''n''. Euclid's lemma suffices to prove that every number has a unique factorization into prime numbers. To see this, assume the contrary, that there are two independent factorizations of ''L'' into ''m'' and ''n'' prime factors, respectively : Since each prime ''p'' divides ''L'' by assumption, it must also divide one of the ''q'' factors; since each ''q'' is prime as well, it must be that ''p'' = ''q''. Iteratively dividing by the ''p'' factors shows that each ''p'' has an equal counterpart ''q''; the two prime factorizations are identical except for their order. The unique factorization of numbers into primes has many applications in mathematical proofs, as shown below.


Linear Diophantine equations

Diophantine equation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
s are equations in which the solutions are restricted to integers; they are named after the 3rd-century Alexandrian mathematician
Diophantus Diophantus of Alexandria ( grc, Διόφαντος ὁ Ἀλεξανδρεύς; born probably sometime between AD 200 and 214; died around the age of 84, probably sometime between AD 284 and 298) was an Alexandria Alexandria ( or ; ar, ال ...
. A typical ''linear'' Diophantine equation seeks integers ''x'' and ''y'' such that : where ''a'', ''b'' and ''c'' are given integers. This can be written as an equation for ''x'' in
modular arithmetic #REDIRECT Modular arithmetic #REDIRECT Modular arithmetic#REDIRECT Modular arithmetic In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure ( ...
: : Let ''g'' be the greatest common divisor of ''a'' and ''b''. Both terms in ''ax'' + ''by'' are divisible by ''g''; therefore, ''c'' must also be divisible by ''g'', or the equation has no solutions. By dividing both sides by ''c''/''g'', the equation can be reduced to Bezout's identity : where ''s'' and ''t'' can be found by the
extended Euclidean algorithm In arithmetic Arithmetic (from the Ancient Greek, Greek wikt:en:ἀριθμός#Ancient Greek, ἀριθμός ''arithmos'', 'number' and wikt:en:τική#Ancient Greek, τική wikt:en:τέχνη#Ancient Greek, έχνη ''tiké échne', 'art' ...
. This provides one solution to the Diophantine equation, ''x''1 = ''s'' (''c''/''g'') and ''y''1 = ''t'' (''c''/''g''). In general, a linear Diophantine equation has no solutions, or an infinite number of solutions. To find the latter, consider two solutions, (''x''1, ''y''1) and (''x''2, ''y''2), where : or equivalently : Therefore, the smallest difference between two ''x'' solutions is ''b''/''g'', whereas the smallest difference between two ''y'' solutions is ''a''/''g''. Thus, the solutions may be expressed as : : . By allowing ''u'' to vary over all possible integers, an infinite family of solutions can be generated from a single solution (''x''1, ''y''1). If the solutions are required to be ''positive'' integers (''x'' > 0, ''y'' > 0), only a finite number of solutions may be possible. This restriction on the acceptable solutions allows some systems of Diophantine equations with more unknowns than equations to have a finite number of solutions; this is impossible for a
system of linear equations In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
when the solutions can be any
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
(see
Underdetermined system In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
).


Multiplicative inverses and the RSA algorithm

A
finite field In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
is a set of numbers with four generalized operations. The operations are called addition, subtraction, multiplication and division and have their usual properties, such as
commutativity In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

commutativity
,
associativity In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a Validity (logic), valid rule ...
and
distributivity In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
. An example of a finite field is the set of 13 numbers using
modular arithmetic #REDIRECT Modular arithmetic #REDIRECT Modular arithmetic#REDIRECT Modular arithmetic In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure ( ...
. In this field, the results of any mathematical operation (addition, subtraction, multiplication, or division) is reduced modulo 13; that is, multiples of 13 are added or subtracted until the result is brought within the range 0–12. For example, the result of 5 × 7 = 35 mod 13 = 9. Such finite fields can be defined for any prime ''p''; using more sophisticated definitions, they can also be defined for any power ''m'' of a prime ''p'' ''m''. Finite fields are often called Galois fields, and are abbreviated as GF(''p'') or GF(''p'' ''m''). In such a field with ''m'' numbers, every nonzero element ''a'' has a unique
modular multiplicative inverse In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer is an integer such that the product is Congruence relation#Basic example, congruent to 1 with respect to the modulus .. In the standard notatio ...
, ''a''−1 such that This inverse can be found by solving the congruence equation ''ax'' ≡ 1 mod ''m'', or the equivalent linear Diophantine equation : This equation can be solved by the Euclidean algorithm, as described above. Finding multiplicative inverses is an essential step in the
RSA algorithm RSA (Rivest–Shamir–Adleman) is a public-key cryptography, public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym RSA comes from the surnames of Ron Rivest, Adi Shamir, and Leonard ...
, which is widely used in
electronic commerce E-commerce (electronic commerce) is the activity of electronically The field of electronics is a branch of physics and electrical engineering that deals with the emission, behaviour and effects of electrons using electronic devices. Electronic ...
; specifically, the equation determines the integer used to decrypt the message. Although the RSA algorithm uses
rings Ring most commonly refers either to a hollow circular shape or to a high-pitched sound. It thus may refer to: *Ring (jewellery), a circular, decorative or symbolic ornament worn on fingers, toes, arm or neck Ring may also refer to: Sounds * Ri ...
rather than fields, the Euclidean algorithm can still be used to find a multiplicative inverse where one exists. The Euclidean algorithm also has other applications in
error-correcting code In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and soft ...
s; for example, it can be used as an alternative to the
Berlekamp–Massey algorithm The Berlekamp–Massey algorithm is an algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used ...

Berlekamp–Massey algorithm
for decoding BCH and Reed–Solomon codes, which are based on Galois fields.


Chinese remainder theorem

Euclid's algorithm can also be used to solve multiple linear Diophantine equations. Such equations arise in the
Chinese remainder theorem In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of the ...
, which describes a novel method to represent an integer ''x''. Instead of representing an integer by its digits, it may be represented by its remainders ''x''''i'' modulo a set of ''N'' coprime numbers ''m''''i'': : \begin x_1 & \equiv x \pmod \\ x_2 & \equiv x \pmod \\ & \,\,\,\vdots \\ x_N & \equiv x \pmod \,. \end The goal is to determine ''x'' from its ''N'' remainders ''x''''i''. The solution is to combine the multiple equations into a single linear Diophantine equation with a much larger modulus ''M'' that is the product of all the individual moduli ''m''''i'', and define ''M''''i'' as : M_i = \frac M . Thus, each ''M''''i'' is the product of all the moduli ''except'' ''m''''i''. The solution depends on finding ''N'' new numbers ''h''''i'' such that : M_i h_i \equiv 1 \pmod \,. With these numbers ''h''''i'', any integer ''x'' can be reconstructed from its remainders ''x''''i'' by the equation : x \equiv (x_1 M_1 h_1 + x_2 M_2 h_2 + \cdots + x_N M_N h_N) \pmod M \,. Since these numbers ''h''''i'' are the multiplicative inverses of the ''M''''i'', they may be found using Euclid's algorithm as described in the previous subsection.


Stern–Brocot tree

The Euclidean algorithm can be used to arrange the set of all positive
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ) ...
s into an infinite
binary search tree In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of c ...

binary search tree
, called the
Stern–Brocot tree In number theory, the Stern–Brocot tree is an Binary tree#Types of binary trees, infinite complete binary tree (graph theory), tree in which the vertex (graph theory), vertices correspond bijection, one-for-one to the positive number, positive ...
. The number 1 (expressed as a fraction 1/1) is placed at the root of the tree, and the location of any other number ''a''/''b'' can be found by computing gcd(''a'',''b'') using the original form of the Euclidean algorithm, in which each step replaces the larger of the two given numbers by its difference with the smaller number (not its remainder), stopping when two equal numbers are reached. A step of the Euclidean algorithm that replaces the first of the two numbers corresponds to a step in the tree from a node to its right child, and a step that replaces the second of the two numbers corresponds to a step in the tree from a node to its left child. The sequence of steps constructed in this way does not depend on whether ''a''/''b'' is given in lowest terms, and forms a path from the root to a node containing the number ''a''/''b''. This fact can be used to prove that each positive rational number appears exactly once in this tree. For example, 3/4 can be found by starting at the root, going to the left once, then to the right twice: : \begin & \gcd(3,4) & \leftarrow \\ = & \gcd(3,1) & \rightarrow \\ = & \gcd(2,1) & \rightarrow \\ = & \gcd(1,1). \end The Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called the . The difference is that the path is reversed: instead of producing a path from the root of the tree to a target, it produces a path from the target to the root.


Continued fractions

The Euclidean algorithm has a close relationship with
continued fraction In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
s. The sequence of equations can be written in the form : \begin \frac a b &= q_0 + \frac b \\ \frac b &= q_1 + \frac \\ \frac &= q_2 + \frac \\ & \,\,\, \vdots \\ \frac &= q_k + \frac \\ & \,\,\, \vdots \\ \frac &= q_N\,. \end The last term on the right-hand side always equals the inverse of the left-hand side of the next equation. Thus, the first two equations may be combined to form :\frac a b = q_0 + \cfrac 1 \,. The third equation may be used to substitute the denominator term ''r''1/''r''0, yielding :\frac a b = q_0 + \cfrac 1 \,. The final ratio of remainders ''r''''k''/''r''''k''−1 can always be replaced using the next equation in the series, up to the final equation. The result is a continued fraction :\frac a b = q_0 + \cfrac 1 = [ q_0; q_1, q_2, \ldots , q_N ] \,. In the worked example #Worked example, above, the gcd(1071, 462) was calculated, and the quotients ''q''''k'' were 2, 3 and 7, respectively. Therefore, the fraction 1071/462 may be written :\frac = 2 + \cfrac 1 = [2; 3, 7] as can be confirmed by calculation.


Factorization algorithms

Calculating a greatest common divisor is an essential step in several integer factorization algorithms, such as Pollard's rho algorithm, Shor's algorithm, Dixon's factorization method and the Lenstra elliptic curve factorization. The Euclidean algorithm may be used to find this GCD efficiently. Continued fraction factorization uses continued fractions, which are determined using Euclid's algorithm.


Algorithmic efficiency

The computational efficiency of Euclid's algorithm has been studied thoroughly. This efficiency can be described by the number of division steps the algorithm requires, multiplied by the computational expense of each step. The first known analysis of Euclid's algorithm is due to A. A. L. Reynaud in 1811, who showed that the number of division steps on input (''u'', ''v'') is bounded by ''v''; later he improved this to ''v''/2  + 2. Later, in 1841, Pierre Joseph Étienne Finck, P. J. E. Finck showed that the number of division steps is at most 2 log2 ''v'' + 1, and hence Euclid's algorithm runs in time polynomial in the size of the input. Émile Léger, in 1837, studied the worst case, which is when the inputs are consecutive Fibonacci numbers. Finck's analysis was refined by
Gabriel Lamé Gabriel Lamé (22 July 1795 – 1 May 1870) was a French mathematician who contributed to the theory of partial differential equation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity ( ...

Gabriel Lamé
in 1844, who showed that the number of steps required for completion is never more than five times the number ''h'' of base-10 digits of the smaller number ''b''. In the uniform cost model (suitable for analyzing the complexity of gcd calculation on numbers that fit into a single machine word), each step of the algorithm takes constant time, and Lamé's analysis implies that the total running time is also ''O''(''h''). However, in a model of computation suitable for computation with larger numbers, the computational expense of a single remainder computation in the algorithm can be as large as ''O''(''h''2). In this case the total time for all of the steps of the algorithm can be analyzed using a telescoping series, showing that it is also ''O''(''h''2). Modern algorithmic techniques based on the Schönhage–Strassen algorithm for fast integer multiplication can be used to speed this up, leading to quasilinear time, quasilinear algorithms for the GCD.


Number of steps

The number of steps to calculate the GCD of two natural numbers, ''a'' and ''b'', may be denoted by ''T''(''a'', ''b'')., p. 344 If ''g'' is the GCD of ''a'' and ''b'', then ''a'' = ''mg'' and ''b'' = ''ng'' for two coprime numbers ''m'' and ''n''. Then : as may be seen by dividing all the steps in the Euclidean algorithm by ''g''. By the same argument, the number of steps remains the same if ''a'' and ''b'' are multiplied by a common factor ''w'': ''T''(''a'', ''b'') = ''T''(''wa'', ''wb''). Therefore, the number of steps ''T'' may vary dramatically between neighboring pairs of numbers, such as T(''a'', ''b'') and T(''a'', ''b'' + 1), depending on the size of the two GCDs. The recursive nature of the Euclidean algorithm gives another equation : where ''T''(''x'', 0) = 0 by assumption.


Worst-case

If the Euclidean algorithm requires ''N'' steps for a pair of natural numbers ''a'' > ''b'' > 0, the smallest values of ''a'' and ''b'' for which this is true are the Fibonacci numbers ''F''''N''+2 and ''F''''N''+1, respectively., p. 343 More precisely, if the Euclidean algorithm requires ''N'' steps for the pair ''a'' > ''b'', then one has ''a'' ≥ ''F''''N''+2 and ''b'' ≥ ''F''''N''+1. This can be shown by mathematical induction, induction. If ''N'' = 1, ''b'' divides ''a'' with no remainder; the smallest natural numbers for which this is true is ''b'' = 1 and ''a'' = 2, which are ''F''2 and ''F''3, respectively. Now assume that the result holds for all values of ''N'' up to ''M'' − 1. The first step of the ''M''-step algorithm is ''a'' = ''q''0''b'' + ''r''0, and the Euclidean algorithm requires ''M'' − 1 steps for the pair ''b'' > ''r''0. By induction hypothesis, one has ''b'' ≥ ''F''''M''+1 and ''r''0 ≥ ''F''''M''. Therefore, ''a'' = ''q''0''b'' + ''r''0 ≥ ''b'' + ''r''0 ≥ ''F''''M''+1 + ''F''''M'' = ''F''''M''+2, which is the desired inequality. This proof, published by
Gabriel Lamé Gabriel Lamé (22 July 1795 – 1 May 1870) was a French mathematician who contributed to the theory of partial differential equation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity ( ...

Gabriel Lamé
in 1844, represents the beginning of
computational complexity theory Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by ...
, and also the first practical application of the Fibonacci numbers. This result suffices to show that the number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10). For if the algorithm requires ''N'' steps, then ''b'' is greater than or equal to ''F''''N''+1 which in turn is greater than or equal to ''φ''''N''−1, where ''φ'' is the
golden ratio In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ...

golden ratio
. Since ''b'' ≥ ''φ''''N''−1, then ''N'' − 1 ≤ log''φ''''b''. Since log10''φ'' > 1/5, (''N'' − 1)/5 < log10''φ'' log''φ''''b'' = log10''b''. Thus, ''N'' ≤ 5 log10''b''. Thus, the Euclidean algorithm always needs less than Big O notation, ''O''(''h'') divisions, where ''h'' is the number of digits in the smaller number ''b''.


Average

The average number of steps taken by the Euclidean algorithm has been defined in three different ways. The first definition is the average time ''T''(''a'') required to calculate the GCD of a given number ''a'' and a smaller natural number ''b'' chosen with equal probability from the integers 0 to ''a'' − 1 :T(a) = \frac 1 a \sum_ T(a, b). However, since ''T''(''a'', ''b'') fluctuates dramatically with the GCD of the two numbers, the averaged function ''T''(''a'') is likewise "noisy". To reduce this noise, a second average ''τ''(''a'') is taken over all numbers coprime with ''a'' :\tau(a) = \frac 1 \sum_ T(a, b). There are ''φ''(''a'') coprime integers less than ''a'', where ''φ'' is Euler's totient function. This tau average grows smoothly with ''a'' :\tau(a) = \frac\ln 2 \ln a + C + O(a^) with the residual error being of order ''a''−(1/6) + ''ε'', where ''ε'' is infinitesimal. The constant ''C'' (''Porter's Constant'') in this formula equals :C= -\frac 1 2 + \frac\left(4\gamma -\frac\zeta'(2) + 3\ln 2 - 2\right) \approx 1.467 where ''γ'' is the Euler–Mascheroni constant and ζ' is the derivative of the Riemann zeta function. The leading coefficient (12/π2) ln 2 was determined by two independent methods. Since the first average can be calculated from the tau average by summing over the divisors ''d'' of ''a'' : T(a) = \frac 1 a \sum_ \varphi(d) \tau(d) it can be approximated by the formula :T(a) \approx C + \frac \ln 2 \left(\ln a - \sum_ \frac d\right) where Λ(''d'') is the von Mangoldt function, Mangoldt function. A third average ''Y''(''n'') is defined as the mean number of steps required when both ''a'' and ''b'' are chosen randomly (with uniform distribution) from 1 to ''n'' :Y(n) = \frac 1 \sum_^n \sum_^n T(a, b) = \frac 1 n \sum_^n T(a). Substituting the approximate formula for ''T''(''a'') into this equation yields an estimate for ''Y''(''n'') : Y(n) \approx \frac \ln 2 \ln n + 0.06.


Computational expense per step

In each step ''k'' of the Euclidean algorithm, the quotient ''q''''k'' and remainder ''r''''k'' are computed for a given pair of integers ''r''''k''−2 and ''r''''k''−1 : The computational expense per step is associated chiefly with finding ''q''''k'', since the remainder ''r''''k'' can be calculated quickly from ''r''''k''−2, ''r''''k''−1, and ''q''''k'' : The computational expense of dividing ''h''-bit numbers scales as ''O''(''h''(''ℓ''+1)), where ''ℓ'' is the length of the quotient., pp. 257–261 For comparison, Euclid's original subtraction-based algorithm can be much slower. A single integer division is equivalent to the quotient ''q'' number of subtractions. If the ratio of ''a'' and ''b'' is very large, the quotient is large and many subtractions will be required. On the other hand, it has been shown that the quotients are very likely to be small integers. The probability of a given quotient ''q'' is approximately ln, ''u''/(''u'' − 1), where ''u'' = (''q'' + 1)2. For illustration, the probability of a quotient of 1, 2, 3, or 4 is roughly 41.5%, 17.0%, 9.3%, and 5.9%, respectively. Since the operation of subtraction is faster than division, particularly for large numbers, the subtraction-based Euclid's algorithm is competitive with the division-based version. This is exploited in the binary GCD algorithm, binary version of Euclid's algorithm. Combining the estimated number of steps with the estimated computational expense per step shows that the Euclid's algorithm grows quadratically (''h''2) with the average number of digits ''h'' in the initial two numbers ''a'' and ''b''. Let ''h''0, ''h''1, ..., ''h''''N''−1 represent the number of digits in the successive remainders ''r''0, ''r''1, ..., ''r''''N''−1. Since the number of steps ''N'' grows linearly with ''h'', the running time is bounded by : O\Big(\sum_h_i(h_i-h_+2)\Big)\subseteq O\Big(h\sum_(h_i-h_+2) \Big) \subseteq O(h(h_0+2N))\subseteq O(h^2).


Alternative methods

Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity. For comparison, the efficiency of alternatives to Euclid's algorithm may be determined. One inefficient approach to finding the GCD of two natural numbers ''a'' and ''b'' is to calculate all their common divisors; the GCD is then the largest common divisor. The common divisors can be found by dividing both numbers by successive integers from 2 to the smaller number ''b''. The number of steps of this approach grows linearly with ''b'', or exponentially in the number of digits. Another inefficient approach is to find the prime factors of one or both numbers. As noted #Greatest common divisor, above, the GCD equals the product of the prime factors shared by the two numbers ''a'' and ''b''. Present methods for integer factorization, prime factorization are also inefficient; many modern cryptography systems even rely on that inefficiency. The binary GCD algorithm is an efficient alternative that substitutes division with faster operations by exploiting the binary numeral system, binary representation used by computers. However, this alternative also scales like big-O notation, ''O''(''h''²). It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way., pp. 77–79, 81–85, 425–431 Additional efficiency can be gleaned by examining only the leading digits of the two numbers ''a'' and ''b''. The binary algorithm can be extended to other bases (''k''-ary algorithms), with up to fivefold increases in speed. Lehmer's GCD algorithm uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases. A recursive approach for very large integers (with more than 25,000 digits) leads to quasilinear time, quasilinear integer GCD algorithms, such as those of Schönhage, and Stehlé and Zimmermann. These algorithms exploit the 2×2 matrix form of the Euclidean algorithm given #Matrix method, above. These quasilinear methods generally scale as


Generalizations

Although the Euclidean algorithm is used to find the greatest common divisor of two natural numbers (positive integers), it may be generalized to the real numbers, and to other mathematical objects, such as
polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

polynomial
s, quadratic integers and Hurwitz quaternions. In the latter cases, the Euclidean algorithm is used to demonstrate the crucial property of unique factorization, i.e., that such numbers can be factored uniquely into irreducible elements, the counterparts of prime numbers. Unique factorization is essential to many proofs of number theory.


Rational and real numbers

Euclid's algorithm can be applied to
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s, as described by Euclid in Book 10 of his ''Euclid's Elements, Elements''. The goal of the algorithm is to identify a real number such that two given real numbers, and , are integer multiples of it: and , where and are
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
s. This identification is equivalent to finding an integer relation algorithm, integer relation among the real numbers and ; that is, it determines integers and such that . Euclid uses this algorithm to treat the question of Commensurability (mathematics), incommensurable lengths. The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders are real numbers, although the quotients are integers as before. Second, the algorithm is not guaranteed to end in a finite number of steps. If it does, the fraction is a rational number, i.e., the ratio of two integers :\frac = \frac = \frac, and can be written as a finite continued fraction . If the algorithm does not stop, the fraction is an irrational number and can be described by an infinite continued fraction . Examples of infinite continued fractions are the
golden ratio In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ...

golden ratio
and the square root of 2, square root of two, . The algorithm is unlikely to stop, since almost all ratios of two real numbers are irrational. An infinite continued fraction may be truncated at a step to yield an approximation to that improves as is increased. The approximation is described by Convergent (continued fraction), convergents ; the numerator and denominators are coprime and obey the recurrence relation :\begin m_k &= q_k m_ + m_ \\ n_k &= q_k n_ + n_, \end where and are the initial values of the recursion. The convergent is the best
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ) ...
approximation to with denominator : : \left, \frac - \frac\ < \frac.


Polynomials

Polynomials in a single variable ''x'' can be added, multiplied and factored into irreducible polynomials, which are the analogs of the prime numbers for integers. The greatest common divisor polynomial of two polynomials and is defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm. The basic procedure is similar to that for integers. At each step , a quotient polynomial and a remainder polynomial are identified to satisfy the recursive equation :r_(x) = q_k(x)r_(x) + r_k(x), where and . Each quotient polynomial is chosen such that each remainder is either zero or has a degree that is smaller than the degree of its predecessor: . Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps. The last nonzero remainder is the greatest common divisor of the original two polynomials, and . For example, consider the following two quartic polynomials, which each factor into two quadratic polynomials :\begin a(x) &= x^4 - 4x^3 + 4x^2 - 3x + 14 = (x^2 - 5x + 7)(x^2 + x + 2) \qquad \text\\ b(x) &= x^4 + 8x^3 + 12x^2 + 17x + 6 = (x^2 + 7x + 3)(x^2 + x + 2). \end polynomial long division, Dividing by yields a remainder . In the next step, is divided by yielding a remainder . Finally, dividing by yields a zero remainder, indicating that is the greatest common divisor polynomial of and , consistent with their factorization. Many of the applications described above for integers carry over to polynomials. The Euclidean algorithm can be used to solve linear Diophantine equations and Chinese remainder problems for polynomials; continued fractions of polynomials can also be defined. The polynomial Euclidean algorithm has other applications, such as Sturm chains, a method for counting the zero of a function, zeros of a polynomial that lie inside a given Interval (mathematics), real interval. This in turn has applications in several areas, such as the Routh–Hurwitz stability criterion in control theory. Finally, the coefficients of the polynomials need not be drawn from integers, real numbers or even the complex numbers. For example, the coefficients may be drawn from a general field, such as the finite fields described above. The corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.


Gaussian integers

The Gaussian integers are complex numbers of the form , where and are ordinary
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
sThe phrase "ordinary integer" is commonly used for distinguishing usual integers from Gaussian integers, and more generally from
algebraic integer In algebraic number theory Algebraic number theory is a branch of number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777 ...
s.
and is the imaginary unit, square root of negative one. By defining an analog of the Euclidean algorithm, Gaussian integers can be shown to be uniquely factorizable, by the argument #Bézout's identity, above. Reprinted in and This unique factorization is helpful in many applications, such as deriving all Pythagorean triples or proving Fermat's theorem on sums of two squares. In general, the Euclidean algorithm is convenient in such applications, but not essential; for example, the theorems can often be proven by other arguments. The Euclidean algorithm developed for two Gaussian integers and is nearly the same as that for ordinary integers, but differs in two respects. As before, the task at each step is to identify a quotient and a remainder such that :r_k = r_ - q_k r_, where , where , and where every remainder is strictly smaller than its predecessor: . The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are complex numbers. The quotients are generally found by rounding the real and complex parts of the exact ratio (such as the complex number ) to the nearest integers. The second difference lies in the necessity of defining how one complex remainder can be "smaller" than another. To do this, a norm (mathematics), norm function is defined, which converts every Gaussian integer into an ordinary integer. After each step of the Euclidean algorithm, the norm of the remainder is smaller than the norm of the preceding remainder, . Since the norm is a nonnegative integer and decreases with every step, the Euclidean algorithm for Gaussian integers ends in a finite number of steps. The final nonzero remainder is , the Gaussian integer of largest norm that divides both and ; it is unique up to multiplication by a unit, or . Many of the other applications of the Euclidean algorithm carry over to Gaussian integers. For example, it can be used to solve linear Diophantine equations and Chinese remainder problems for Gaussian integers; continued fractions of Gaussian integers can also be defined.


Euclidean domains

A set of elements under two binary operations, denoted as addition and multiplication, is called a
Euclidean domain In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a #Definition, Euclidean function which allows a suitable generalization of the Euclidean division of ...
if it forms a commutative ring and, roughly speaking, if a generalized Euclidean algorithm can be performed on them. The two operations of such a ring need not be the addition and multiplication of ordinary arithmetic; rather, they can be more general, such as the operations of a group (mathematics), mathematical group or monoid. Nevertheless, these general operations should respect many of the laws governing ordinary arithmetic, such as commutative property, commutativity, associative property, associativity and distributive property, distributivity. The generalized Euclidean algorithm requires a ''Euclidean function'', i.e., a mapping from into the set of nonnegative integers such that, for any two nonzero elements and in , there exist and in such that and . Examples of such mappings are the absolute value for integers, the degree for univariate polynomials, and the norm for Gaussian integers #Gaussian integers, above. The basic principle is that each step of the algorithm reduces ''f'' inexorably; hence, if can be reduced only a finite number of times, the algorithm must stop in a finite number of steps. This principle relies on the well-ordering property of the non-negative integers, which asserts that every non-empty set of non-negative integers has a smallest member. The fundamental theorem of arithmetic applies to any Euclidean domain: Any number from a Euclidean domain can be factored uniquely into irreducible elements. Any Euclidean domain is a unique factorization domain (UFD), although the converse is not true. The Euclidean domains and the UFD's are subclasses of the GCD domains, domains in which a greatest common divisor of two numbers always exists. In other words, a greatest common divisor may exist (for all pairs of elements in a domain), although it may not be possible to find it using a Euclidean algorithm. A Euclidean domain is always a
principal ideal domain In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
(PID), an integral domain in which every
ideal Ideal may refer to: Philosophy * Ideal (ethics) An ideal is a principle A principle is a proposition or value that is a guide for behavior or evaluation. In law Law is a system A system is a group of Interaction, interacting ...
is a
principal ideal In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
. Again, the converse is not true: not every PID is a Euclidean domain. The unique factorization of Euclidean domains is useful in many applications. For example, the unique factorization of the Gaussian integers is convenient in deriving formulae for all Pythagorean triples and in proving Fermat's theorem on sums of two squares. Unique factorization was also a key element in an attempted proof of Fermat's Last Theorem published in 1847 by Gabriel Lamé, the same mathematician who analyzed the efficiency of Euclid's algorithm, based on a suggestion of Joseph Liouville. Lamé's approach required the unique factorization of numbers of the form , where and are integers, and is an th root of 1, that is, . Although this approach succeeds for some values of (such as , the
Eisenstein integer In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
s), in general such numbers do factor uniquely. This failure of unique factorization in some cyclotomic fields led Ernst Kummer to the concept of ideal numbers and, later,
Richard Dedekind Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German German(s) may refer to: Common uses * of or related to Germany * Germans, Germanic ethnic group, citizens of Germany or people of German ancestry * For citiz ...
to
ideals Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring considered ...
.


Unique factorization of quadratic integers

The quadratic integer rings are helpful to illustrate Euclidean domains. Quadratic integers are generalizations of the Gaussian integers in which the imaginary unit ''i'' is replaced by a number . Thus, they have the form , where and are integers and has one of two forms, depending on a parameter . If does not equal a multiple of four plus one, then :\omega = \sqrt D . If, however, ''D'' does equal a multiple of four plus one, then :\omega = \frac . If the function corresponds to a field norm, norm function, such as that used to order the Gaussian integers #Gaussian integers, above, then the domain is known as ''Norm-Euclidean field, norm-Euclidean''. The norm-Euclidean rings of quadratic integers are exactly those where is one of the values −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, or 73. The cases and yield the
Gaussian integer In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as . This inte ...
s and
Eisenstein integer In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
s, respectively. If is allowed to be any Euclidean function, then the list of possible values of for which the domain is Euclidean is not yet known. The first example of a Euclidean domain that was not norm-Euclidean (with ) was published in 1994. In 1973, Weinberger proved that a quadratic integer ring with is Euclidean if, and only if, it is a
principal ideal domain In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
, provided that the generalized Riemann hypothesis holds.


Noncommutative rings

The Euclidean algorithm may be applied to some noncommutative rings such as the set of Hurwitz quaternions. Let and represent two elements from such a ring. They have a common right divisor if and for some choice of and in the ring. Similarly, they have a common left divisor if and for some choice of and in the ring. Since multiplication is not commutative, there are two versions of the Euclidean algorithm, one for right divisors and one for left divisors. Choosing the right divisors, the first step in finding the by the Euclidean algorithm can be written :\rho_0 = \alpha - \psi_0\beta = (\xi - \psi_0\eta)\delta, where represents the quotient and the remainder. This equation shows that any common right divisor of and is likewise a common divisor of the remainder . The analogous equation for the left divisors would be :\rho_0 = \alpha - \beta\psi_0 = \delta(\xi - \eta\psi_0). With either choice, the process is repeated as above until the greatest common right or left divisor is identified. As in the Euclidean domain, the "size" of the remainder (formally, its Quaternion#Conjugation, the norm, and reciprocal, norm) must be strictly smaller than , and there must be only a finite number of possible sizes for , so that the algorithm is guaranteed to terminate. Most of the results for the GCD carry over to noncommutative numbers. For example,
Bézout's identity In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical ...
states that the right can be expressed as a linear combination of and . In other words, there are numbers and such that :\Gamma_\text = \sigma\alpha + \tau\beta. The analogous identity for the left GCD is nearly the same: :\Gamma_\text = \alpha\sigma + \beta\tau. Bézout's identity can be used to solve Diophantine equations. For instance, one of the standard proofs of
Lagrange's four-square theorem Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer square number, squares. That is, the squares form an additive basis of order four. :p = a_0^2 + a_ ...
, that every positive integer can be represented as a sum of four squares, is based on quaternion GCDs in this way.


See also

* Euclidean rhythm, a method for using the Euclidean algorithm to generate musical rhythms


Notes


References


Bibliography

* * * * * . See also Vorlesungen über Zahlentheorie * * * * * * * * * *


External links


Demonstrations of Euclid's algorithm
*
Euclid's Algorithm
at cut-the-knot *
The Euclidean Algorithm
at MathPages
Euclid's Game
at cut-the-knot
Music and Euclid's algorithm
{{DEFAULTSORT:Euclidean Algorithm Number theoretic algorithms Articles with example pseudocode Articles containing proofs Euclid, Algorithm