Euclidean algorithm

This article is about the greatest common divisor. For the mathematics of space, see Euclidean geometry.

Animation of the Euclidean algorithm for 252 and 105. The crossbars represent multiples of 21, the greatest common divisor (GCD). In each step, the smaller number is subtracted from the larger number, until one number is reduced to zero. The remaining number is the GCD.

In mathematics, the Euclidean algorithm^[a] (also called Euclid's algorithm) is an efficient method for computing the greatest common divisor (GCD), also known as the greatest common factor (GCF) or highest common factor (HCF). It is named after the Greek mathematician Euclid, who described it in Books VII and X of his Elements.

The GCD of two numbers is the largest number that divides both of them without leaving a remainder. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the smaller number is subtracted from the larger number. For example, 21 is the GCD of 252 and 105 (252 = 21 × 12; 105 = 21 × 5); since 252 − 105 = 147, the GCD of 147 and 105 is also 21. Since the larger of the two numbers is reduced, repeating this process gives successively smaller numbers until one of them is zero. When that occurs, the GCD is the remaining nonzero number. By reversing the steps in the Euclidean algorithm, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., 21 = 5 × 105 + (−2) × 252. This important property is known as Bézout's identity.

The earliest surviving description of the Euclidean algorithm is in Euclid's Elements (c. 300 BC), making it one of the oldest numerical algorithms still in common use. 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 integers and polynomials in one variable. This led to modern abstract algebraic notions such as Euclidean domains. The Euclidean algorithm has been generalized further to other mathematical structures, such as knots and multivariate polynomials.

The Euclidean algorithm has many theoretical and practical applications. It may be used to generate almost all the most important traditional musical rhythms used in different cultures throughout the world. It is a key element of the RSA algorithm, a public-key encryption method widely used in electronic commerce. It is used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences (Chinese remainder theorem) or multiplicative inverses of a finite field. The Euclidean algorithm can also be used in constructing continued fractions, in the Sturm chain method for finding real roots of a polynomial, and in several modern integer factorization algorithms. Finally, it is a basic tool for proving theorems in modern number theory, such as Lagrange's four-square theorem and the fundamental theorem of arithmetic (unique factorization).

Euclid's algorithm computes the GCD of large numbers efficiently, because it never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844, and marks the beginning of computational complexity theory. Methods for improving the algorithm's efficiency were developed in the 20th century.

Background

Greatest common divisor

The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers 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), 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 also used for other mathematical concepts, such as two-dimensional vectors.

If GCD(a, b) = 1, then a and b are said to be coprime. This property is independent of whether a and b are themselves prime numbers. 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.

A 24-by-60 rectangle is covered with ten 12-by-12 square tiles, where 12 is the GCD of 24 and 60. More generally, an a-by-b rectangle can be covered with square tiles of side-length c only if c is a common divisor of a and b.

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 can 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 can be defined as the common divisor 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, 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 can be defined as the product of the prime factors shared by the two numbers. For example, since 462 can be factored into 2 × 3 × 7 × 11 and 1071 can be factored into 3 × 3 × 7 × 17, the greatest common divisor of 462 and 1071 equals 21 = 3 × 7, the product of their shared prime factors. If two numbers have no prime factors in common, their greatest common divisor is 1—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 of large integers is believed to be such a difficult problem that many modern cryptography systems are based upon it.

A more subtle definition of the GCD is helpful in advanced mathematics, particularly ring theory. The greatest common divisor g  of two numbers a and b is also their smallest integer multiple, that is, the smallest number of the form ua + vb where u and v are integers. It follows that the set of all integer multiples of a and b (all numbers ua + vb) is the same as the set of all integer multiples of g (mg, where m is an integer). In modern mathematical language, the ideal formed by a and b is a principal ideal generated by g. 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, which can be calculated by taking the GCDs of pairs of numbers. For example,

GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b).

Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers.

Induction, recursion and infinite descent

Three related mathematical methods are used in the arguments below: induction, recursion and infinite descent. Induction is often used to prove a theorem for all natural numbers n. This approach begins by showing that, if the theorem holds for n, it also holds for n + 1. Therefore, if the theorem holds for one case (typically, n = 1), it holds for all higher cases (n = 2, 3, etc.). A recursion is an equation relating numbers that form a series a₁, a₂, a₃, etc. The n^th term in the series, a_n, is often expressed in terms of earlier terms of the series, such as a_n−1. For example, the Fibonacci numbers are defined recursively; each term is the sum of the two preceding terms: F_n = F_n−1 + F_n−2. Several equations associated with the Euclidean algorithm are recursive. Finally, in infinite descent, a given solution in natural numbers is used to construct a solution with smaller natural numbers. However, the solutions cannot shrink indefinitely, since there are only a finite number of natural numbers below the initial natural numbers. Therefore, either the original solution was impossible, or the construction of smaller solutions must end. The latter argument is used to show that the Euclidean algorithm for natural numbers must end in a finite number of steps.

Description

Procedure

The Euclidean algorithm is iterative, meaning that the answer is found in a series of steps; the output of each step is used as an input for the next step. 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 kth step is to find a quotient q_k and remainder r_k such that the equation is satisfied

r_k−2 = q_k r_k−1 + r_k

where 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 is smaller than the r_k−1.

In the initial step (k = 0), the remainders r₋₂ and r₋₁ 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₀ of the initial step, and so on. Thus, the algorithm can be written as a sequence of equations

a = q₀ b + r₀

b = q₁ r₀ + r₁

r₀ = q₂ r₁ + r₂

r₁ = q₃ r₂ + r₃

…

If a is smaller than b, the first step of the algorithm swaps the numbers. For example, if a < b, the initial quotient q₀ equals zero, and the remainder r₀ 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₀ 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

r_N−2 = q_N r_N−1

since the final remainder r_N is zero. r_N−1 also divides its next predecessor r_N−3

r_N−3 = q_N−1 r_N−2 + r_N−1

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₀, since r₀ = a − q₀b = mc − q₀nc = (m − q₀n)c. An analogous argument shows that c also divides the subsequent remainders r₁, r₂, 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:

g = GCD(a, b) = GCD(b, r₀) = GCD(r₀, r₁) = … = GCD(r_N−2, r_N−1) = r_N−1

Worked example

Animation of the algorithm. The initial green rectangle has dimensions a = 1071 and b = 462. Square 462×462 tiles are added until a green 462×147 rectangle remains. This is tiled with square 147×147 tiles until a 21×147 rectangle remains. This third rectangle is tiled with 21×21 square tiles, leaving no remainder. Thus, 21 is the greatest common divisor of 1071 and 462.

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₀ = 2), leaving a remainder of 147

1071 = 2 × 462 + 147.

Then multiples of 147 are subtracted from 462 until the remainder is less than 147. Three multiples can be subtracted (q₁ = 3), leaving a remainder of 21

462 = 3 × 147 + 21.

Then multiples of 21 are subtracted from 147 until the remainder is less than 21. Seven multiples can be subtracted (q₂ = 7), leaving no remainder

147 = 7 × 21 + 0.

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

Step k	Equation	Quotient and remainder
0	1071 = q0 462 + r0	q0 = 2 and r0 = 147
1	462 = q1 147 + r1	q1 = 3 and r1 = 21
2	147 = q2 21 + r2	q2 = 7 and r2 = 0; algorithm ends

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₀-by-b residual rectangle untiled, where r₀<b. We then attempt to tile the residual rectangle with r₀-by-r₀ square tiles. This leaves a second residual rectangle r₁-by-r₀, which we attempt to tile using r₁-by-r₁ 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).

Calculating the quotients and remainders

See also: Modulo operation and Division algorithm

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

r_k−2 = q_k r_k−1 + r_k

where the magnitude of r_k is strictly less than that of r_k−1. The division algorithm ensures that such a quotient and remainder always exist. The division algorithm for natural numbers also states that q_k and r_k are unique, but that is not needed for the Euclidean algorithm.

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. A more efficient approach uses integer division and the modulo operation to calculate the quotient and remainder, respectively. The modulo operation gives the remainder after dividing two numbers; thus,

r_k ≡ r_k−2 mod r_k−1

The remainder is equivalent to the congruence class in modular arithmetic.

Implementations

Implementations of the algorithm may be expressed in pseudocode. 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 kth 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 dummy variable 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.

In the subtraction-based version defined by Euclid, the remainder calculation (b = a mod b) is replaced by repeated subtraction.

function gcd(a, b)
    if a = 0
       return b
    while b ≠ 0
        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)

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

r_k−2 = q_k r_k−1 + r_k

assumed that r_k−1 > r_k > 0. However, an alternative negative remainder e_k can be computed

r_k−2 = (q_k + 1) r_k−1 + e_k

where r_k−1 is assumed to be positive. If |e_k| < |r_k|, then r_k is replaced by e_k. As shown by Leopold Kronecker, this version requires the fewest number of steps of any version of Euclid's algorithm.

Historical development

The Euclidean algorithm was probably invented centuries before Euclid, shown here holding dividers

The Euclidean algorithm is one of the oldest algorithms still in common use. 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 numbers. 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, and 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, 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 written by mathematicians in the school of Pythagoras. The algorithm was probably known by Eudoxus of Cnidus (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.

Centuries later, Euclid's algorithm was discovered independently both in India and in China, primarily to solve Diophantine equations that arise in astronomy and making accurate calendars. In the late fifth century, the Indian mathematician and astronomer Aryabhata described the algorithm as the "pulverizer", perhaps because of its effectiveness in solving Diophantine equations. Although a special case of the Chinese remainder theorem had already been described by Chinese mathematician and astronomer Sun Tzu, the general solution was published by Qin Jiushao in his 1247 book Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections). The Euclidean algorithm was first described 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 fractions. The extended Euclidean algorithm was published by the English mathematician Nicholas Saunderson, who attributed it to 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 integers and Eisenstein integers. In 1815, Carl Gauss used the Euclidean algorithm to demonstrate unique factorization of Gaussian integers, although his work was first published in 1832. Gauss mentioned the algorithm in his Disquisitiones Arithmeticae (published 1801), but only as a method for continued fractions. Peter Dirichlet seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory. 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. Dirichlet's lectures on number theory were edited and extended by Richard Dedekind, who used Euclid's algorithm to study algebraic integers, a new general type of number. For example, Dedekind was the first to prove Fermat's two-square theorem using the unique factorization of Gaussian integers. Dedekind also defined the concept of a Euclidean domain, a number system in which a generalized version of the Euclidean algorithm can be defined (as described below). In the closing decades of the 19th century, however, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of ideals.

"[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day."

Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd edition (1981), p. 318.

Other applications of Euclid's algorithm were developed in the 19th century. In 1829, Charles Sturm showed that the algorithm was useful in the Sturm chain method for counting the real roots of polynomials in any given interval.

The Euclidean algorithm was the first integer relation algorithm, which is a method for finding integer relations between commensurate real numbers. Several novel integer relation algorithms have been developed in recent years, such as the Ferguson–Forcade algorithm (1979) of Helaman Ferguson and R.W. Forcade, and its relatives, the LLL algorithm, the HJLS algorithm, and the PSLQ 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 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₀, q₁, 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.

g = r_N−1 = r_N−3 − q_N−1 r_N−2

Those two remainders can be likewise expressed in terms of their quotients and preceding remainders,

r_N−2 = r_N−4 − q_N−2 r_N−3

r_N−3 = r_N−5 − q_N−3 r_N−4

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

r₂ = r₀ − q₂ r₁

r₁ = b − q₁ r₀

r₀ = a − q₀ b

After all the remainders r₀, r₁, etc. have been substituted, the final equation expresses g as a linear sum of a and b: g = sa + tb. Bézout's identity, and therefore the previous algorithm, can both be generalized to the context of Euclidean domains.

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

mg = msa + mtb

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 of a and b. This GCD definition led to the modern abstract algebraic concepts of a principal ideal (an ideal generated by a single element) and a principal ideal domain (a domain 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. This extension adds two recursive equations to Euclid's algorithm

s_k = s_k−2 − q_k−1s_k−1

t_k = t_k−2 − q_k−1t_k−1

with the starting values

s₋₂ = 1, t₋₂ = 0

s₋₁ = 0, t₋₁ = 1

Using this recursion, Bézout's integers s and t are given by s = s_N and t = t_N, where N is the step on which the algorithm terminates with r_N = 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

r_j = s_j a + t_j b

for all j less than k. The kth step of the algorithm gives the equation

r_k = r_k−2 − q_k−1r_k−1

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

r_k = (s_k−2 a + t_k−2 b) − q_k−1(s_k−1 a + t_k−1 b)

Rearranging this equation yields the recursion formula for step k, as required

r_k = s_k a + t_k b = (s_k−2 − q_k−1s_k−1) a + (t_k−2 − q_k−1t_k−1) b

Matrix method

The integers s and t can also be found using an equivalent matrix method. The sequence of equations of Euclid's algorithm

a = q₀ b + r₀

b = q₁ r₀ + r₁

…

r_N−2 = q_N r_N−1 + 0

can be written as a product of 2-by-2 quotient matrices multiplying a two-dimensional remainder vector

${\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}b\\r_{0}\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}=\cdots =\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}$

Let M represent the product of all the quotient matrices

$\mathbf {M} ={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}$

This simplifies the Euclidean algorithm to the form

${\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}$

To express g as a linear sum of a and b, both sides of this equation can be multiplied by the inverse of the matrix M. The 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{pmatrix}g\\0\end{pmatrix}}=\mathbf {M} ^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}$

Since the top equation gives

g = (−1)^N+1 ( m₂₂ a − m₁₂ b)

the two integers of Bézout's identity are s = (−1)^N+1m₂₂ and t = (−1)^Nm₁₂. 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 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

1 = su + tw

by Bézout's identity. Multiplying both sides by v gives the relation

v = suv + twv = sL + twv

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. 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₁, a₂, …, a_n, then w is also coprime to their product, a₁ × a₂ × … × 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

L = p₁p₂…p_m = q₁q₂…q_n

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

Plot of a linear Diophantine equation, 9x + 12y = 483. The solutions are shown as blue circles.

Diophantine equations are equations in which the solutions are restricted to integers; they are named after the third-century Alexandrian mathematician Diophantus. A typical linear Diophantine equation seeks integers x and y such that

ax + by = c

where a, b and c are given integers. This can be written as an equation for x in modular arithmetic

ax ≡ c mod b.

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

sa + tb = g

where s and t can be found by the extended Euclidean algorithm. This provides one solution to the Diophantine equation, x₁ = s (c/g) and y₁ = 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₁, y₁) and (x₂, y₂)

ax₁ + by₁ = c = ax₂ + by₂

or equivalently

a(x₁ − x₂) = b(y₂ − y₁).

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

x = x₁ − bt/g

y = y₁ + at/g.

By allowing t to vary over all possible integers, an infinite family of solutions can be generated from a single solution (x₁, y₁). 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 systems of Diophantine equations to be solved with more unknowns than equations; this is impossible for a system of linear equations when the solutions can be any real number.

Multiplicative inverses and the RSA algorithm

A finite field 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, associativity and distributivity. An example of a finite field is the set of 13 numbers {0, 1, 2, …, 12} using modular arithmetic. In this field, the results of any mathematical operation (addition/subtraction/multiplication/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, a⁻¹ such that aa⁻¹ = a⁻¹a ≡ 1 mod m. This inverse can be found by solving the congruence equation ax ≡ 1 mod m, or the equivalent linear Diophantine equation

ax + my = 1

This equation can be solved by the Euclidean algorithm, as described above. Finding multiplicative inverses is an essential step in the RSA algorithm, which is widely used in electronic commerce; specifically, the equation determines the integer used to decrypt the message. Note that although the RSA algorithm uses rings 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 codes; for example, it can be used as an alternative to the 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, 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.

x₁ ≡ x mod m₁

x₂ ≡ x mod m₂

…

x_N ≡ x mod m_N

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 the M_i

M_i = M / m_i

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_ih_i ≡ 1 mod m_i

With these numbers h_i, any integer x can be reconstructed from its remainders x_i by the equation

x ≡ (x₁M₁h₁ + x₂M₂h₂ + … + x_NM_Nh_N ) mod 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.

Continued fractions

The Euclidean algorithm has a close relationship with continued fractions. The sequence of equations can be written in the form

a/b = q₀ + r₀/b

b/r₀ = q₁ + r₁/r₀

r₀/r₁ = q₂ + r₂/r₁

…

r_k−2/r_k−1 = q_k + r_k/r_k−1

…

r_N−2/r_N−1 = q_N

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

a/b = q₀ + 1/(q₁ + r₁/r₀)

The third equation may be used to substitute the denominator term r₁/r₀, yielding

a/b = q₀ + 1/(q₁ + 1/(q₂ + r₂/r₁))

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

a/b = q₀ + 1/(q₁ + 1/(q₂ + 1/(… + 1/q_N))…) = [q₀; q₁, q₂, …, q_N]

In the 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

1071/462 = 2 + 1/(3 + 1/7) = [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

Number of steps in the Euclidean algorithm for GCD(x,y). Red points indicate relatively few steps (quick), whereas yellow, green and blue points indicate successively more steps (slow).

The computational efficiency of Euclid's algorithm has been studied thoroughly. This efficiency can be described by the number of steps the algorithm requires, multiplied by the computational expense of each step. As shown first by Gabriel Lamé in 1844, the number of steps required for completion is never more than five times the number h of digits (base 10) of the smaller number b. Since the computational expense of each step is also typically of order h, the overall expense grows like h².

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). If g is the GCD of a and b, then a = mg and b = ng for two coprime numbers m and n. Then

T(a, b) = T(m, n)

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

T(a, b) = 1 + T(b, r₀) = 2 + T(r₀, r₁) = … = N + T(r_N−2, r_N−1) = N + 1

where T(x, 0) = 0 by assumption.

Worst-case number of steps

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. This can be shown by 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₂ and F₃, 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₀b + r₀, and the second step is b = q₁r₀ + r₁. Since the algorithm is recursive, it required M − 1 steps to find GCD(b, r₀) and their smallest values are F_M+1 and F_M. The smallest value of a is therefore when q₀ = 1, which gives a = b + r₀ = F_M+1 + F_M = F_M+2. This proof, published by Gabriel Lamé in 1844, represents the beginning of computational complexity theory, 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. Since b ≥ φ^N−1, then N − 1 ≤ log_φb. Since log₁₀φ > 1/5, (N − 1)/5 < log₁₀φ log_φb = log₁₀b. Thus, N ≤ 5 log₁₀b. Thus, the Euclidean algorithm always needs less than O(h) divisions, where h is the number of digits in the smaller number b.

Average number of steps

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 _{0\leq b<a}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}{\varphi (a)}}\sum _{0\leq b<a,\mathrm {GCD} (a,b)=1}T(a,b).$

There are φ(a) coprime integers less than a, where φ is Euler's totient function. This tau average grows smoothly with a

τ(a) = (12/π²) ln 2 ln a + C + O(a^{−(1/6) + ε})

with the residual error being of order a^{−(1/6) + ε}, where ε is infinitesimal. The constant C in this formula equals

C = −(1/2) + 6 (ln 2/π²)( 4γ − 24π²ζ '(2) + 3 ln 2 − 2) ≈ 1.467

where γ is the Euler–Mascheroni constant and ζ' is the derivative of the Riemann zeta function. The leading coefficient (12/π²) 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 _{d|a}\varphi (d)\tau (d)$

it can be approximated by the formula

T(a) ≈ C + (12/π²) ln 2 ( ln a − Σ_d|a Λ(d)/d )

where Λ(d) is the 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}{n^{2}}}\sum _{a=1}^{n}\sum _{b=1}^{n}T(a,b)={\frac {1}{n}}\sum _{a=1}^{n}T(a).$

Substituting the approximate formula for T(a) into this equation yields an estimate for Y(n)

Y(n) ≈ (12/π²) 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

r_k−2 = q_k r_k−1 + r_k.

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

r_k = r_k−2 − q_k r_k−1.

The computational expense of dividing h-bit numbers scales as O(h(ℓ+1)), where ℓ is the length of the quotient.

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)². 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 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²) with the average number of digits h in the initial two numbers a and b. Let h₀, h₁, …, h_N−1 represent the number of digits in the successive remainders r₀, r₁, …, r_N−1. Since the number of steps N grows linearly with h, the running time is bounded by

$O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2}).$

Efficiency of 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 above, the GCD equals the product of the prime factors shared by the two numbers a and b. Present methods for 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 representation used by computers. However, this alternative also scales like O(h²). It is generally faster on real computers, but it scales in the same way as the Euclidean algorithm. 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.

A recursive approach for very large integers (with more than 25,000 digits) leads to subquadratic 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 above. These subquadratic methods generally scale as O(h (log h)² (log log h)).

Other number systems

As described above, the Euclidean algorithm is used to find the greatest common divisor of two natural numbers (positive integers). However, it may be generalized to the real numbers, and to more exotic number systems such as polynomials, 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 numbers, as described by Euclid in Book 10 of his Elements. The goal of the algorithm is to identify a real number g such that two given real numbers, a and b, are integer multiples of it: a = mg and b = ng, where m and n are integers. This identification is equivalent to finding an integer relation among the real numbers a and b; that is, it determines integers s and t such that sa + tb = 0. Euclid uses this algorithm to treat the question of incommensurable lengths.

The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders r_k are real numbers, although the quotients q_k are integers as before. Second, the algorithm is not guaranteed to end in a finite number N of steps. If it does, the fraction a/b is a rational number, i.e., the ratio of two integers

a/b = mg/ng = m/n

and can be written as a finite continued fraction [q₀; q₁, q₂, …, q_N]. If the algorithm does not stop, the fraction a/b is an irrational number and can be described by an infinite continued fraction [q₀; q₁, q₂, …]. Examples of infinite continued fractions are the golden ratio φ = [1; 1, 1, …] and the square root of two, √2 = [1; 2, 2, …]. Generally speaking, the algorithm is unlikely to stop, since almost all ratios a/b of two real numbers are irrational.

An infinite continued fraction may be truncated at a step k [q₀; q₁, q₂, …, q_k] to yield an approximation to a/b that improves as k is increased. The approximation is described by convergents m_k/n_k; the numerator and denominators are coprime and obey the recursion

m_k = q_k m_k−1 + m_k−2

n_k = q_k n_k−1 + n_k−2

where m₋₁ = n₋₂ = 1 and m₋₂ = n₋₁ = 0 are the initial values of the recursion. The convergent m_k/n_k is the best rational number approximation to a/b with denominator n_k:

$\left|{\frac {a}{b}}-{\frac {m_{k}}{n_{k}}}\right|<{\frac {1}{n_{k}^{2}}}.$

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 g(x) of two polynomials a(x) and b(x) is defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm. The basic procedure is similar to integers. At each step k, a quotient polynomial q_k(x) and a remainder polynomial r_k(x) are identified to satisfy the recursive equation

r_k−2(x) = q_k(x) r_k−1(x) + r_k(x)

where r₋₂(x) = a(x) and r₋₁(x) = b(x). The quotient polynomial is chosen so that the leading term of q_k(x) r_k−1(x) equals the leading term of r_k−2(x); this ensures that the degree of each remainder is smaller than the degree of its predecessor deg[r_k(x)] < deg[r_k−1(x)]. 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 final nonzero remainder is the greatest common divisor of the original two polynomials, a(x) and b(x).

For example, consider the following two quartic polynomials, which each factor into two quadratic polynomials

a(x) = x⁴ − 4x³ + 4 x² − 3x + 14 = (x² − 5x + 7)(x² + x + 2)

and

b(x) = x⁴ + 8x³ + 12x² + 17x + 6 = (x² + 7x + 3)(x² + x + 2).

Dividing a(x) by b(x) yields a remainder r₀(x) = x³ + (2/3) x² + (5/3) x − (2/3). In the next step, b(x) is divided by r₀(x) yielding a remainder r₁(x) = x² + x + 2. Finally, dividing r₀(x) by r₁(x) yields a zero remainder, indicating that r₁(x) is the greatest common divisor polynomial of a(x) and b(x), 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 as well, such as Sturm chains, a method for counting the number of real roots of a polynomial within a given interval on the real axis. This 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 GF(p) described above. The corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.

Gaussian integers

Distribution of Gaussian primes u + vi in the complex plane, with norms u² + v² less than 500

The Gaussian integers are complex numbers of the form α = u + vi, where u and v are ordinary integers and i is the 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 above. 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 normal integers, but differs in two respects. As before, the task at each step k is to identify a quotient q_k and a remainder r_k such that

r_k = r_k−2 − q_k r_k−1

where r_k−2 = α, r_k−1 = β, and every remainder is strictly smaller than its predecessor, |r_k| < |r_k−1|. The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are complex numbers. The quotients q_k 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, we define a norm function f(u + vi) = u² + v², which converts every Gaussian integer u + vi into a normal integer. After each step k of the Euclidean algorithm, the norm of the remainder f(r_k) is smaller than the norm of the preceding remainder, f(r_k−1). 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 GCD(α,β), the Gaussian integer of largest norm that divides both α and β; it is unique up to multiplication by a unit, ±1 or ±i.

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, + and ·, is called a Euclidean domain if it forms a commutative ring R 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 mathematical group or monoid. Nevertheless, these general operations should respect many of the laws governing ordinary arithmetic, such as commutativity, associativity and distributivity.

The generalized Euclidean algorithm requires a Euclidean function, i.e., a mapping f from R into the set of nonnegative integers such that, for any two nonzero elements a and b in R, there exist q and r in R such that a = qb + r and f(r) < f(b). An example of this mapping is the norm function used to order the Gaussian integers above. The function f can be the magnitude of the number, or the degree of a polynomial. The basic principle is that each step of the algorithm reduces f inexorably; hence, if f can be reduced only a finite number of times, the algorithm must stop in a finite number of steps. This principle relies heavily on the natural well-ordering of the non-negative integers; roughly speaking, this requires that every 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 are a subclass 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 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 (PID), an integral domain in which every ideal is a principal ideal. 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 x + ωy, where ω = e^2iπ/n is the nth root of 1, that is, ωⁿ = 1. Although this approach succeeds for some values of n (such as n=3, the Eisenstein integers), in general such numbers do not factor uniquely. This failure of unique factorization in some cyclotomic fields led Ernst Kummer to the concept of ideal numbers and, later, Richard Dedekind to ideals.

Unique factorization of quadratic integers

Distribution of Eisenstein primes u + vω in the complex plane, with norms less than 500. The number ω equals the cube root of 1.

The quadratic integers 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 u + v ω, where u and v are integers and ω has one of two forms, depending on a parameter D. If D does not equal a multiple of four plus one (such as 5, 17, or −19), then

ω = √D.

If, however, D does equal a multiple of four plus one, then

ω = (1 + √D)/2.

If the function f corresponds to a norm function, such as that used to order the Gaussian integers above, then the domain of such numbers is Euclidean only for a finite set of D values: D = −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 or 73. Such domains are known as norm-Euclidean. The quadratic integers with D = −1 and −3 are known as the Gaussian integers and Eisenstein integers, respectively.

If f is allowed to be any Euclidean function, then the list of possible D values for which the domain is Euclidean is not yet known. The first example of a Euclidean domain that was not norm-Euclidean (with D=69) was published in 1994. In 1973, Weinberger proved that a domain is Euclidean if and only if it is a principal ideal domain, provided that the generalized Riemann hypothesis holds; Weinberger's proof was generalized in 2004 to remove this restriction.

Noncommutative rings

It is also possible to apply the Euclidean algorithm to 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 GCD(α, β) by the Euclidean algorithm can be written

ρ₀ = α − ψ₀β = (ξ − ψ₀η)δ

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

ρ₀ = α − βψ₀ = δ(ξ − ηψ₀)

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 ρ₀ 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 states that the right GCD(α, β) can be expressed as a linear combination of α and β. In other words, there are numbers σ and τ such that

Γ_right = σα + τβ

The analogous identity for the left GCD is nearly the same

Γ_left = ασ + βτ

Bézout's identity can be used to solve Diophantine equations.

Generalizations to other mathematical structures

The Euclidean algorithm can be applied in knot theory.

The Euclidean algorithm has three general features that together ensure it will not continue indefinitely. First, it can be written as a sequence of recursive equations

r_k = r_k−2 − q_k r_k−1

where each remainder is strictly smaller than its predecessor, |r_k| < |r_k−1|. Second, the size of each remainder has a strict lower limit, such as |r_k| ≥ 0. Third, there is only a finite number of sizes smaller than a given remainder |r_k|. Generalizations of Euclid's algorithm with these basic features have been applied to other mathematical structures, such as tangles and transfinite ordinal numbers.

An important generalization of the Euclidean algorithm is the concept of a Gröbner basis in algebraic geometry. As shown above, the GCD g of two integers a and b is the generator of their ideal. In other words, for any choice of the integers s and t, there is another integer m such that

sa + tb = mg.

Although this remains true when s, t, m, a and b represent polynomials of a single variable, it is not true for rings of more than one variable. In that case, a finite set of generator polynomials g₁, g₂, etc. can be defined such that any linear combination of two multivariable polynomials a and b can be expressed as multiples of the generators

sa + tb = Σ_k m_kg_k

where s, t and m_k are multivariable polynomials. Any such multivariable polynomial f can be expressed as such a sum of generator polynomials plus a unique remainder polynomial r, sometimes called the normal form of polynomial f

f = r + Σ_k q_kg_k

although the quotient polynomials q_k may not be unique. The set of these generator polynomials is known as a Gröbner basis.

See also

• Binary GCD algorithm
• Extended Euclidean algorithm
• Greatest common divisor of two polynomials
• Integer relation algorithm
• Lehmer's GCD algorithm

Notes

• a. ^{^} Some widely used textbooks, such as I. N. Herstein's Topics in Algebra and Serge Lang's Algebra, use the term "Euclidean algorithm" to refer to the division algorithm. However, the division algorithm is a theorem, not an algorithm.

Bibliography

• Cohen H (1993). A Course in Computational Algebraic Number Theory. New York: Springer-Verlag. ISBN 0-387-55640-0.
• Cohn H (1962). Advanced Number Theory. New York: Dover. ISBN 0-486-64023-X.
• Cormen TH, Leiserson CE, Rivest RL, and Stein C (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw–Hill. ISBN 0262032937.{{cite book}}: CS1 maint: multiple names: authors list (link)
• Cox D, Little J, and O'Shea D (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (2nd ed.). Springer-Verlag. ISBN 0-387-94680-2.{{cite book}}: CS1 maint: multiple names: authors list (link)
• Dirichlet PGL (1894). Richard Dedekind (ed.). Vorlesungen über Zahlentheorie. Braunschweig: Vieweg.
• Hardy GH, Wright EM [revised by D.R. Heath-Brown and J.H. Silverman]. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford: Clarendon Press.
• Knuth D (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison–Wesley. ISBN 0201896842.
• LeVeque WJ (1977). Fundamentals of Number Theory. New York: Dover. ISBN 0-486-68906-9.
• Mollin RA (2008). Fundamental Number Theory with Applications (2nd ed.). Boca Raton: Chapman & Hall/CRC. ISBN 9781420066593.
• Ore Ø (1948). Number Theory and Its History. New York: McGraw–Hill.
• Rosen KH (2000). Elementary Number Theory and its Applications (4th ed.). Reading, MA: Addison–Wesley. ISBN 0201870738.
• Schroeder MR (2005). Number Theory in Science and Communication (4th ed.). Springer-Verlag. ISBN 0387158006.
• Stark H (1978). An Introduction to Number Theory. MIT Press. ISBN 0-262-69060-8.
• Stillwell J (1997). Numbers and Geometry. New York: Springer-Verlag. ISBN 0-387-98289-2.
• Tattersall JJ (2005). Elementary number theory in nine chapters. Cambridge: Cambridge University Press. ISBN 9780521850148.
• Uspensky JV, Heaslet MA (1939). Elementary Number Theory. New York: McGraw–Hill.

External links

• Demonstrations of Euclid's algorithm
• Weisstein, Eric W. "Euclidean Algorithm". MathWorld.
• Euclid's Algorithm at cut-the-knot
• Euclid's algorithm at PlanetMath.
• The Euclidean Algorithm at MathPages
• Euclid's Game at cut-the-knot
• Music and Euclid's algorithm