Euclidean algorithm
From Wikipedia, the free encyclopedia
The Euclidean algorithm (also called Euclid's algorithm) is an efficient algorithm for computing the greatest common divisor (GCD) of two numbers. If g represents the GCD(a, b), then g is the largest number that divides both a and b without leaving a remainder. In other words, a and b are both multiples of g, and can be written as a = mg and b = ng, where m and n have no divisor in common. The Euclidean algorithm is the oldest known algorithm and has many theoretical and practical applications, such as modern integer factorization algorithms and the RSA algorithm, a publickey encryption method widely used in electronic commerce.
The Euclidean algorithm is a series of steps in which the GCD(a, b) is related to the GCD of two smaller numbers. In particular, it rests on the fact that the GCD of two numbers remains the same when one is subtracted from the other. If q multiples of b are subtracted from a, the remainder r is divisible by g, because r = mg − qng = (m − qn)g. Although this is true for any integer q, the Euclidean algorithm chooses q to make the remainder r as small as possible. It follows that GCD(a, b) = GCD(b, r), where r is smaller than b.
For illustration, let a = 1989 and b = 867. The Euclidean algorithm begins by subtracting multiples of b from a until the nonnegative remainder r_{0} is less than b. In this case, q_{0}=2 and r_{0} = aq_{0}b = 255, which is less than b.
 GCD(1989, 867) = GCD (867, 255)
In the next step, b takes the place of a, and r_{0} takes the place of b. The algorithm subtracts multiples of r_{0} from b until the nonnegative remainder r_{1} is less than r_{0}. In this case, q_{1}=3 and r_{1} = bq_{1}r_{0} = 102, which is less than r_{0}.
 GCD(1989, 867) = GCD(867, 255) = GCD(255, 102)
The process continues until the remainder is zero, which must happen in a finite number of steps for natural numbers and many other types of numbers. In this case, the final nonzero remainder is g=51, the greatest common divisor.
 GCD(1989, 867) = GCD(867, 255) = GCD(255, 102) = GCD(102, 51) = GCD(51, 0)
The Euclidean algorithm is considered efficient, because the number of steps required increases logarithmically with the size of the two integers. It is never more than five times the number of digits (base 10) in the smaller integer.
The Euclidean algorithm is the oldest known algorithm. (An algorithm is a set of rules for calculating a quantity, together with a proof that the rules always produce the correct result.) The ancient Greek geometer Euclid described it in Books 7 and 10 of his Elements (c. 300 BC), applying it to both natural numbers and real numbers. The algorithm may have been developed centuries before Euclid, possibly by mathematicians in the school of Pythagoras. The algorithm was rediscovered in India and China to aid in solving Diophantine equations (equations that require integer solutions), which occur in many areas of science and mathematics. The algorithm was generalized to other types of numbers, such as algebraic integers, in the 19th century.
The Euclidean algorithm has many theoretical and practical applications. It is a fundamental tool in modern number theory, for example, in proving the unique factorization of a set of numbers or in deriving theorems such as Lagrange's foursquare theorem. It can be used to solve various Diophantine equations, such as finding numbers that satisfy multiple congruences (Chinese remainder theorem) or multiplicative inverses of a finite field. By reversing the algorithm, g can be expressed as a linear sum of a and b, that is, g = sa + tb, where s and t are integers (Bézout's identity). The Euclidean algorithm is also used to construct continued fractions, an accurate approximation method, and in the Sturm chain method for finding the real roots of a polynomial. Finally, it can be used to classify commutative rings in modern abstract algebra; a set of numbers are said to form a Euclidean domain, if an analog of Euclid's algorithm can be defined on them.
Contents 
[edit] Background
[edit] 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. The greatest common divisor is often written as GCD(a, b) or more simply, (a, b).^{[1]}
If GCD(a, b) = 1, then a and b are said to be coprime, or relatively prime.^{[2]} This property is independent of whether a and b are themselves prime numbers.^{[3]} For example, neither 6 = 2×3 nor 35 = 5×7 are prime numbers, since they both have two prime factors. Nevertheless, 6 and 35 are coprime; no natural number divides both 6 and 35, since they have no prime factors in common.
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 q could be factored out of m and n to make g greater. The GCD of any multiple q of the original numbers is q times the original GCD^{[4]}
 GCD (qa, qb) = q GCD(a, b)
More generally, any other number c that divides both a and b must also divide g. Indeed, this property can be taken as the definition of the greatest common divisor,^{[5]} since it implies that g is greater than any other common divisor.
The GCD can be visualized as follows. Imagine a rectangular area a by b covered exactly by square d×d tiles, where d is the sidelength of a square tile. Since the area is covered exactly (with no overhang), the number d must divide both a and b leaving no remainder. The greatest common divisor g equals the largest value of d for which this is possible. For illustration, a 24×60 rectangular area can be covered exactly by several types of square tiles: 1×1 tiles, 2×2 tiles, 3×3 tiles, 6×6 tiles or 12×12 tiles. Thus, 12 is the greatest common divisor of 24 and 60.
The GCD of two numbers a and b is the product of the shared prime factors of the two numbers.^{[6]} For example, 1029 can be factored into 3×7×7×7 and 1071 can be factored into 3×3×7×17; hence, the GCD of 1029 and 1071 is 3×7, the product of the prime factors they have in common. If two numbers have no shared prime factors, 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;^{[7]}^{[8]} integer factorization is a difficult problem for large numbers.
The GCD is related to the least common multiple (LCM) by the equation^{[9]}
 GCD(a,b) × LCM(a,b) = a×b
Euclid's algorithm provides an efficient method for computing the LCM, by dividing the product a×b by their GCD. Alternatively, the GCD of a and b may be computed by dividing their product a×b by their LCM.
The GCD and LCM have several common uses, including reducing fractions and finding the lowest common denominator of fractions. For illustration, the fraction 74/111 can be reduced to 2/3 by dividing the numerator and denominator by their GCD, 37. Similarly, the sum of 1/74 + 5/111 can be calculated by converting both terms to a common denominator, 3/222 + 10/222 = 13/222; here, 222 is the LCM of 74 and 111.
[edit] Division algorithm
The Euclidean algorithm requires that, for any two numbers i and j, it is always possible to find a quotient q and remainder r such that
 i = qj + r
where the magnitude of r is strictly less than that of j. The division algorithm ensures that such a quotient and remainder always exist, a necessary condition for the Euclidean algorithm. The division algorithm for natural numbers also states that q and r are unique, but that is not needed for the Euclidean algorithm.
[edit] Description
The Euclidean algorithm consists of a series of steps. Each step k begins with two nonnegative integers i and j, and the goal is to find two new nonnegative integers q_{k} and r_{k} such that
 i = q_{k} j + r_{k}
where r_{k}<j. The two derived numbers q_{k} and r_{k} are called the quotient and the remainder, respectively, of step k.
In the initial step (k=0), the numbers i and j are taken to be the numbers a and b for which the GCD is sought, where one may assume that a>b. In the second step, (k=1), i and j are taken to be b and the remainder r_{0} of the initial step. In the next and subsequent steps, i and j are taken to be the remainders from the two previous steps, e.g., r_{0} and r_{1} for the next step. Thus, the algorithm can be written as a sequence of equations
 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}
 ...
 r_{k−2} = q_{k} r_{k−1} + r_{k}
If a is not larger than b as assumed, then the first step of the algorithm swaps the numbers. For example, if a<b, the initial quotient q_{0} equals zero, and the remainder q_{0} is a. The next step divides the smaller initial number into the larger initial number, exactly as above.
The sequence of equations ends once a remainder r_{N} is zero. The sequence must end in a finite number of steps N, because every remainder is nonnegative and strictly smaller than its predecessor (r_{k} < r_{k−1}); there are a finite number of nonnegative integers between any remainder and zero. The final nonzero remainder r_{N−1} is the greatest common divisor of a and b, as shown by the following twostep argument.
In the first step, r_{N−1} divides both a and b. To demonstrate this, 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, by definition. It follows that r_{N−1} 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 righthand 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_{k} divide a and b, since they leave a remainder. Since r_{N−1} is a common divisor of a and b, it is smaller than or equal to the greatest common divisor: 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 higher remainders r_{1}, r_{2}, etc. and, in particular, the final nonzero remainder r_{N−1}. 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, that r_{N−1} ≤ g, it follows that g = r_{N−1}. Thus, g is the greatest common divisor of all the succeeding pairs^{[10]}
 g = GCD(a, b) = GCD(b, r_{0}) = GCD(r_{0}, r_{1}) = ... = GCD(r_{N−3}, r_{N−2}) = GCD(r_{N−2}, r_{N−1}) = r_{N−1}
This chain of equations is the basis for a recursive implementation of Euclid's algorithm.^{[11]}
[edit] Visualization
The Euclidean algorithm can be visualized in terms of the rectangletiling analogy given above for the greatest common divisor. Assume that we wish to cover an abyb rectangle with square tiles exactly, where a is the larger of the two numbers. We first attempt to tile the rectangle using bbyb square tiles; however, this leaves an r_{0}byb residual rectangle untiled, where r_{0}<b. We then attempt to tile the residual rectangle with r_{0}byr_{0} square tiles. This leaves a second residual rectangle r_{1}byr_{0}, which we attempt to tile using r_{0}byr_{0} 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.
[edit] Calculating the quotients and remainders

See also: Modulo operation and Division algorithm
The basic task in the Euclidean algorithm is to compute the quotient and remainder
 i = q_{k} j + r_{k}
for a given pair of nonnegative integers, i and j. Euclid solves this problem by repeated subtraction; that is, he subtracts j from i iteratively until the remainder r_{k} is smaller than j. This approach is guaranteed to work in advanced number systems such as commutative rings, where the only defined operations are addition, subtraction and multiplication.
Modern computers have more efficient methods for computing the quotient and remainder of two integers. The usual approach is to use 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} ≡ i mod j
Computational efficiency can also be gained by defining the algorithm recursively, as described below.
[edit] Worked example
The Euclidean algorithm can be used to find the greatest common divisor of the natural numbers 1071 and 1029, which is 21. To begin, multiples of 1029 are subtracted from 1071 until the remainder is less than 1029. Only one such multiple can be subtracted, leaving a remainder of 42
 1071 = 1×1029 + 42
Then multiples of 42 are subtracted from 1029 until the remainder is less than 42. Twentyfour multiples can be subtracted, leaving a remainder of 21
 1029 = 24×42 + 21
Then multiples of 21 are subtracted from 42 until the remainder is less than 21. Two multiples can be subtracted, leaving no remainder
 42 = 2×21 + 0
Since the last remainder is zero, the algorithm ends and 21 is the greatest common divisor of 1071 and 1029.
To relate this example to the general description above, the steps can be written as
Step  Equation  Quotient and remainder 

0  1071 = q_{0} 1029 + r_{0}  q_{0} = 1 and r_{0} = 42 
1  1029 = q_{1} r_{0} + r_{1}  q_{1} = 24 and r_{1} = 21 
2  r_{0} = q_{2} r_{1} + r_{2}  q_{2} = 2 and r_{2} = 0; algorithm ends 
[edit] Implementations
Implementations of the algorithm may be expressed in pseudocode. For example, the divisionbased version may be programmed as
function gcd(a, b) while b ≠ 0 t := b b := a mod b a := t return a
At the end of each loop iteration, the variable b holds the latest remainder r_{k}, whereas the variable a holds the previous remainder, r_{k−1}. The dummy variable t merely holds the value of r_{k−1} while the new r_{k} is being calculated.
For comparison, the subtractionbased version defined by Euclid would be written as
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 integer division step is replaced by repeated subtraction.
The recursive version is briefer than both
function gcd(a, b) if b = 0 return a else return gcd(b, a mod b)
This recursion is best illustrated by a worked example. The GCD(1071,1029) is calculated from the equivalent GCD(1029, 1071 mod 1029) = GCD(1029, 42). This in turn is calculated from the equivalent GCD(42, 1029 mod 42) = GCD(42, 21). This in turn is calculated from the equivalent GCD(21, 42 mod 21) = GCD(21, 0) = 21. This approach is wellsuited to computers, which generally maintain a stack of function calls.
[edit] 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 absolute value than the typical positive remainder.^{[12]}^{[13]} Previously, one solved the equation
 r_{k−2} = q_{k} r_{k−1} + r_{k}
assuming that r_{k−1} > r_{k} > 0. Assuming that r_{k−1} is positive, an alternative negative remainder s_{k} can be computed
 r_{k−2} = (q_{k} + 1) r_{k−1} + s_{k}
If s_{k} < r_{k}, then r_{k} is replaced by s_{k}. As shown by Leopold Kronecker, this version requires the fewest number of steps of any version of Euclid's algorithm.^{[12]}^{[13]}
[edit] Applications
[edit] Bézout's identity
Bézout's identity states that the greatest common divisor g can be represented as a linear sum of the original two numbers, a and b. In other words, it is 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 nexttolast 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_{2} = r_{0} − q_{2} r_{1}
 r_{1} = b − q_{1} r_{0}
 r_{0} = a − q_{0} b
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 provides yet another definition of the greatest common divisor g of two numbers a and b. Consider the set of all numbers sa + tb, where s and t are integers. By the argument above, every member of the set is an integer multiple of g; consequently, g has the smallest absolute value of any member of the set. This definition is helpful in considering more sophisticated number fields,^{[14]} since it provides a link between the Euclidean algorithm and the concept of a principal ideal.
[edit] Extended Euclidean algorithm
The integers s and t of Bézout's identity can be computed efficiently using the extended Euclidean algorithm. The sequence of equations of Euclid's algorithm
 a = q_{0} b + r_{0}
 b = q_{1} r_{0} + r_{1}
 ...
 r_{k−2} = q_{k} r_{k−1} + r_{k}
 ...
 r_{N−2} = q_{N} r_{N−1} + 0
can be written in a compact matrix form^{[15]}
Let M represent the product of all the quotient matrices
The matrix M can be calculated efficiently, with two multiplications and two additions per step of the Euclidean algorithm. This simplifies the Euclidean algorithm to the form
since the final nonzero remainder r_{N−1} is the greatest common divisor g.
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 inverse is welldefined, since the determinant of M is not zero. Rather, it equals (1)^{N+1}, since it equals the product of the determinants of the quotient matrices, each of which is negative one. Therefore, the vector of the final remainders can be solved using the inverse of M
Since the top equation gives
 g = (1)^{N+1} ( m_{22} a  m_{12} b)
the two integers of Bézout's identity are s = (1)^{N+1}m_{22} and t = (1)^{N}m_{12}.
[edit] Euclid's lemma and unique factorization
Bézout's identity is essential to many higher 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. For 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 righthand side, it must also divide the lefthand side, v. This result is known as Euclid's lemma.^{[16]} Specifically, if a prime number p divides L, 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}.^{[17]}
To prove unique factorization, assume the contrary, namely that there are two independent factorizations of L into m and n prime factors, respectively
 L = p_{1}p_{2}...p_{m} = q_{1}q_{2}...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, and hence m=n.
[edit] Linear Diophantine equations
Diophantine equations are equations in which the solutions are restricted to integers; they are named after the thirdcentury Alexandrian mathematician Diophantus. A typical linear Diophantine equation is to solve for an unknown integer x that satisfies an equation in modular arithmetic
 ax ≡ c mod b
This equation asks to find an integer x such that ax equals c, possibly with the addition or subtraction of multiples of b. In other words, the equation seeks to find unknown integers x and y such that^{[18]}
 ax + by = c
where y is an integer. Let g be the greatest common divisor of a and b. Both terms on the lefthand side 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.^{[19]} 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})
 ax_{1} + by_{1} = c = ax_{2} + by_{2}
or equivalently
 a(x_{1}  x_{2}) = b(y_{2}  y_{1})
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_{1}  bt/g
 y = y_{1} + at/g
By allowing t 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 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.
[edit] Multiplicative inverses and the RSA algorithm
A finite field is a set of numbers that obey the usual laws of addition, subtraction, multiplication and division of real numbers, such as commutativity, associativity and distributivity. A simple example of such 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 012. For example, the result of 5×7 = 35 mod 13 = 9. Such Galois fields can be defined for any prime p, and are denoted as GF(p); using more sophisticated definitions, they can also be defined for any power m of a prime, GF(p^{m}).
In such a field with m numbers, every element a has a unique multiplicative inverse a^{−1} such that aa^{−1} = a^{−1}a ≡ 1 mod m. This inverse can be found by solving the congruence equation ax ≡ 1 mod m,^{[20]} or the equivalent linear Diophantine equation^{[21]}
 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.^{[22]}
[edit] 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 several coprime numbers m_{i}.^{[23]}
 x_{1} ≡ x mod m_{1}
 x_{2} ≡ x mod m_{2}
 ...
 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_{i}h_{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_{1}M_{1}h_{1} + x_{2}M_{2}h_{2} + ... + x_{N}M_{N}h_{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.
[edit] Continued fractions
The Euclidean algorithm has a close relationship with continued fractions.^{[24]} The sequence of equations can be written in the form
 a/b = q_{0} + r_{0}/b
 b/r_{0} = q_{1} + r_{1}/r_{0}
 r_{0}/r_{1} = q_{2} + r_{2}/r_{1}
 ...
 r_{k−2}/r_{k−1} = q_{k} + r_{k}/r_{k−1}
 ...
 r_{N−2}/r_{N1} = q_{N}
The last term on the righthand side always equals the inverse of the lefthand side of the next equation. Thus, the first two equations may be combined to form
 a/b = q_{0} + 1/(q_{1} + r_{1}/r_{0})
The third equation may be used to substitute the denominator term r_{1}/r_{0}, yielding
 a/b = q_{0} + 1/(q_{1} + 1/(q_{2} + r_{2}/r_{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
 a/b = q_{0} + 1/(q_{1} + 1/(q_{2} + 1/(... + 1/q_{N}))...) = [q_{0}; q_{1}, q_{2}, ..., q_{N}]
In the worked example above, the GCD(1071, 1029) was calculated, and the quotients q_{k} were 1, 24 and 2, respectively. Therefore, the fraction 1071/1029 may be written
 1071/1029 = 1 + 1/(24 + 1/2) = [1; 24, 2]
as can be confirmed by calculation.
[edit] Factorization algorithms
Calculating a greatest common divisor is an essential step in several modern factorization algorithms, such as 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.
[edit] Algorithmic efficiency
Euclid's algorithm is not the only algorithm for identifying the GCD of two integers, but it is among the most efficient. Its computational efficiency can be described in terms of the number of steps it requires, multiplied by the computational expense of each step. As shown first by Gabriel Lamé in 1844,^{[25]} the number of steps required for completion is never more than five times the number h of digits (base 10) of the two numbers. Lamé's worstcase calculation represents the beginning of computational complexity theory.^{[26]} Since the computational expense of each step is also typically of order h, the overall expense grows like h^{2}.
[edit] Number of steps
The number of steps to calculate the GCD of two natural numbers, a and b, is usually 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.^{[27]} 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, a mod b) = 1 + T(b, r_{0}) = 2 + T(r_{0}, r_{1}) = ... = N + T(r_{N−2}, r_{N−1}) = N + 1
where T(x, 0) = 0 by assumption.^{[28]}
[edit] Worstcase 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.^{[29]} This can be shown by induction.^{[30]} 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 M1. The first step of the Mstep algorithm is a = q_{0} b + r_{0}, and the second step is b = q_{1} r_{0} + r_{1}. Since the algorithm is recursive, it required M−1 steps to find GCD(b, r_{0}) and their smallest values are F_{M+1} and F_{M}. The smallest value of a is therefore when q_{0} = 1, which gives a = b + r_{0} = F_{M+1} +F_{M} = F_{M+2}. This proof by Gabriel Lamé was the first practical application of the Fibonacci numbers.^{[31]}
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).^{[32]} 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}, where φ is the golden ratio. Since b > φ^{N}, then N < log_{φ} b. Since log_{10} φ > 1/5, N/5 < log_{10} φ log_{φ} b = log_{10} b. Thus, N < log_{10} b. Thus, the Euclidean algorithm always less than O(h) divisions, where h is the number of digits in the input.
[edit] Average number of steps
The average number of steps taken by the Euclidean algorithm has been defined in several ways. One 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^{[33]}
However, since T(a, b) fluctuates dramatically with the GCD of the two numbers, the averaged function T(a) is likewise "noisy".^{[34]}
To reduce this noise, a different average τ(a) is taken over all numbers coprime with a
There are φ(a) coprime integers less than a, where φ is Euler's totient function. This tau average grows steadily with a and is wellapproximated by^{[35]}
 τ(a) ≈ (12/π^{2}) ln 2 ln a + C + O(a^{(1/6) + ε})
where the constant C≈1.467 is given by
 C = (1/2) + 6 (ln 2/π^{2})( 4γ  24π^{2}ζ'(2) + 3 ln 2  2)
where γ is the Euler–Mascheroni constant and ζ' is the derivative of the Riemann zeta function.^{[36]}^{[37]} The leading coefficient (12/π^{2}) ln 2 was determined by two independent methods.^{[38]}^{[39]}
Since the first average can be calculated from the tau average by summing over the divisors d of a^{[40]}
it can be approximated by the formula^{[41]}
 T(a) = C + (12/π^{2}) ln 2 ( ln a  Σ_{da} Λ(d)/d )
where Λ(d) is the Mangoldt function.^{[42]}
Yet another average Y(n) is the mean number of steps required when both a and b are chosen randomly (with uniform distribution) from 1 to n
Substituting the approximate formula for T(a) into this equation yields an estimate for Y(n)^{[43]}
 Y(n) ≈ (12/π^{2}) ln 2 ln n + 0.06
[edit] 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 i and j
 i = q_{k} j + r_{k}
The computational expense per step is associated chiefly with finding q_{k}, since the remainder r_{k} can be calculated quickly from i, j, and q_{k}
 r_{k} = i − q_{k} j
The computational expense of dividing hbit numbers scales as O(h(l+1)), where l is the length of the quotient.
For comparison, Euclid's original subtractionbased 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. In particular, if a and b are successive Fibonacci numbers, Euclid's original algorithm is significantly faster than the usual divisionbased one.
[edit] Overall quadratic efficiency
Combining these two results shows that the computational efficiency of Euclid's algorithm grows like h^{2}. Consider the computation of gcd(a,b) where a and b have at most h bits. 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 N grows linearly with h, the running time is bounded by
[edit] 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. The GCD is then the product of the prime factors that divide both numbers. Prime factorization is also inefficient, and likely scales exponentially with the number of digits.
An efficient alternative, the binary GCD algorithm, exploits the binary representation used by computers to avoid divisions and thereby increase efficiency, although it too is O(n²). It merely shrinks the constant hidden by the bigO notation on many real machines.
Additional efficiency can be gleaned by examining only the leading digits of the two numbers a and b. This approach leads to subquadratic integer GCD algorithms, such as those of Schönhage, Knuth and Schönhage, and Stehlé and Zimmermann. All of these algorithms have the same efficiency; they scale as O(n (log n)^{2} (log log n)).^{[44]}^{[45]}
[edit] Other domains of numbers
[edit] 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.
The realnumber Euclidean algorithm differs from its integer counterpart in two respects. First, all 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_{0}; q_{1}, q_{2}, ..., q_{N}]. If the algorithm does not stop, the fraction a/b is an irrational number and can be decribed by an infinite continued fraction [q_{0}; q_{1}, q_{2}, ...]. 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_{0}; q_{1}, q_{2}, ..., 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_{−1} = n_{−2} = 1 and m_{−2} = n_{−1} = 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}
  (a/b) − (m_{k}/n_{k})  < 1/n_{k}^{2}
[edit] 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 of two such polynomials is defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm.^{[46]} For example, consider the following two quartic polynomials, which both factor into two quadratic polynomials
 a(x) = x^{4}  4x^{3} + 4 x^{2}  3x + 14 = (x^{2}5x+7)(x^{2}+x+2)
and
 b(x) = x^{4} + 8x^{3} + 12x^{2} + 17x + 6 = (x^{2} + 7x + 3)(x^{2} + x + 2).
From this factorization, the greatest common divisor of the polynomials is x^{2} + x + 2.
The GCD polynomial of two polynomials, a(x) and b(x), can be found without factorization using the Euclidean algorithm. The basic procedure are similar to integers; at each step, we identify a quotient q(x) and remainder r(x) so that the equations are satisfied
 a(x) = q_{0}(x) b(x) + r_{0}(x)
 b(x) = q_{1}(x) r_{0}(x) + r_{1}(x)
 r_{0}(x) = q_{2}(x) r_{1}(x) + r_{2}(x)
 etc.
where 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).
In the example above, dividing a(x) by b(x) yields a remainder r_{0}(x) = x^{3} +\(2/3) x^{2} + (5/3) x  (2/3). In the next step, b(x) is divided by r_{0}(x) yielding a remainder r_{1}(x) = x^{2} + x + 2. Finally, dividing r_{0}(x) by r_{1}(x) yields no remainder, indicating that r_{1}(x) is the greatest common divisor polynomial of a(x) and b(x).
Many of the applications described above for integers carry over to polynomials.^{[47]} 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 RouthHurwitz 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.^{[46]}
[edit] Gaussian integers
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.^{[48]} This unique factorization is useful in many applications, such as deriving all Pythagorean triples or proving Fermat's theorem on sums of two squares.^{[49]}
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 basic steps are to identify quotient q_{k} and remainders r_{k} such that
 α = q_{0}β + r_{0}
 β = q_{1}r_{0} + r_{1}
 r_{0} = q_{2}r_{1} + r_{2}
 etc.
where each remainder is smaller than its predecessor. 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^{2} + v^{2}, 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.
The unique factorization of Gaussian integers permits the computation of all possible Pythagorean triples, which are sets of three integers (a, b, c) that satisfy the Pythagorean theorem
 c^{2} = a^{2} + b^{2}
Wellknown examples of Pythagorean triples include (3, 4, 5) and (5, 12, 13). The righthand side may be factored in Gaussian integers
 c^{2} = a^{2} + b^{2} = (a + bi) (a  bi)
Since Gaussian integers factor uniquely, and since the lefthand side c^{2} is a square, then each of the two factors, a + bi and a  bi, must be squares themselves. Thus, the first factor can be written
 a + bi = (u + vi)^{2}
from which two formulae can be derived
 a = u^{2}  v^{2}
 b = 2 uv
If these two equations are satisfied, a and b will always form a Pythagorean triple, as may be verified by substitution. Conversely, for any Pythagorean triple, there must be integers u and v such that the two equations are satisfied. Hence, all possible Pythagorean triples are generated from all possible choices of the integers u and v. For illustration, u = 2 and v = 1 yields the Pythagorean triple (3, 4, 5), whereas the choice u=3 and v=2 yields the triple (5, 12, 13).
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.
[edit] Euclidean domains
A set of elements is called a Euclidean domain if they form a commutative ring and if an analog of Euclid's algorithm can be performed on them. Any number from a Euclidean domain can be factored uniquely into irreducible elements, and thus, any Euclidean domain is a unique factorization domain (UFD); but the converse isn't true. The Euclidean domains are a subset 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. However, again, the converse is not true; not every PID is a Euclidean domain.
For Euclidean domains R, Euclid's algorithm is generalized as follows. A generalized Euclidean algorithm requires a mapping f of R into nonnegative integers such that, for any two nonzero elements a and b of the domain, there exist q and r in R such that a = qb + r and f(r) < f(b). This mapping corresponds to 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.
The quadratic integers are helpful to illustrate the limits of Euclidean domains. Quadratic integers are generalization of the Gaussian integers mentioned above, 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.
The domain of such numbers is Euclidean only for certain values of D. In particular, quadratic integers form a Euclidean domain if and only if D = −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 or 73.^{[50]}
[edit] Fermat's Last Theorem
The Euclidean algorithm has been used to verify Fermat's Last Theorem for specific values of the exponent n. This theorem states that the equation
 x^{n} + y^{n} = z^{n}
has no solutions for any n>2, provided that x, y, z, and n are all integers and that xyz ≠ 0; in other words, none of the variables can be zero. This equation is an example of a nonlinear Diophantine equation.
As with the Pythagorean triples above, this equation can be factored
 (x + y)(x + ωy)(x + ω^{2}y)...(x + ω^{n−1}y) = z^{n}
where ω = e^{2iπ/n} is the n^{th} root of 1, that is,
 ω^{n} = 1
Now assume that the factors on the lefthand side of the equation form a Euclidean domain and can be factored uniquely.
[edit] Noncommutative rings
It is also possible to apply the Euclidean algorithm to noncommutative rings such as the set of Hurwitz quaternions.^{[51]} Since multiplication is not commutative, the right and left divisors must be distinguished. Let α and β represent two numbers from such a ring. Then, 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. The Euclidean algorithm can be defined for either choice of divisor. For example, choosing the right divisors, the first step in finding the GCD(α, β) by the Euclidean algorithm can be written
 ρ_{0} = α  ψ_{0}β = (ξ  ψ_{0}η)δ
where ψ_{0} represents the quotient and ρ_{0} the remainder. This equation shows that any common right divisor of α and β is likewise a common divisor of the remainder ρ_{0}. The analogous equation for the left divisors would be
 ρ_{0} = α  βψ_{0} = δ(ξ  ηψ_{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 ρ_{0} must be strictly smaller than β, and there must be only a finite number of possible sizes for ρ_{0}, 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 suffices to show that the numbers can be factored uniquely, as discussed above. It also can be used to solve Diophantine equations and find multiplicative inverses in finite fields.
[edit] Hurwitz quaternions and the foursquare theorem
The Euclidean algorithm is useful in proving Lagrange's foursquare theorem, by demonstrating the unique factorization of Hurwitz quaternions. Lagrange's theorem states that any natural number can be represented as the sum of four squares
 p = a_{0}^{2} + a_{1}^{2} + a_{2}^{2} + a_{3}^{2}
where the four numbers (a_{0}, a_{1}, a_{2}, a_{3}) are integers. This theorem corresponds to Fermat's theorem on sums of two squares, which can likewise be proven using the unique factorization of Gaussian integers, again demonstrated using the Euclidean algorithm.
The quaternions are defined as a set of numbers α
 α = a_{0} + a_{1} i + a_{2} j + a_{3} k
where the boldfaced numbers i, j, and k have the properties
 i^{2} = j^{2} = k^{2} = ijk = −1
From these definitions, the product ij = k but ji = −k. In other words, multiplication of quaternions is not commutative; the product αβ need not equal βα. The numbers (a_{0}, a_{1}, a_{2}, a_{3}) are real numbers and are called the components of the quaternion. For every quaternion α, a conjugate quaternion ᾶ can be defined
 ᾶ = a_{0} − a_{1} i − a_{2} j − a_{3} k
The product αᾶ = ᾶα is called the norm N(α) of the quaternion, and is a nonnegative real number.
 N(α) = a_{0}^{2} + a_{1}^{2} + a_{2}^{2} + a_{3}^{2}
The norm of a real number (a_{0}, 0, 0, 0) equals the square of the number N = a_{0}^{2}.
The Hurwitz quaternions are the analog of integers for quaternions. They consist of all quaternions with integer components and all quaternions with halfinteger components. These two sets can be combined into a single formula
 α = ½ A_{0} (1 + i + j + k ) + A_{1} i + A_{2} j + A_{3} k
where the four numbers (A_{0}, A_{1}, A_{2}, A_{3}) are all integers. The set of quaternions formed from such four integer components form a ring; in particular, the sum or product of any two such Hurwitz quaternions is likewise a Hurwitz quaternion. The greatest common right or left divisor can be found by the Euclidean algorithm as described in the previous section, where the "size" of the remainder ρ is measured by the norm, which is always an integer.
Thanks to Euler's foursquare identity, the norm of a product of quaternions αβ equals the norm of α times the norm of β
 N(αβ) = N(α) N(β)
Since any natural number can be factored into powers of primes, the foursquare theorem holds for all natural numbers if it is true for all prime numbers. It is true for 2 = 0^{2} + 0^{2} + 1^{2} + 1^{2}. To show this for odd prime integer p, assume that p can be factored in the Hurwitz quaternions
 p = α β
The norms of p, α and β are all nonnegative integers such that
 N(p) = p^{2} = N(αβ) = N(α) N(β)
But the norm has only two factors, both p. Therefore, if p can be factored in Hurwitz quaternions, then p is the sum of four squares
 p = N(α) = a_{0}^{2} + a_{1}^{2} + a_{2}^{2} + a_{3}^{2}
Lagrange demonstrated that any odd prime p can divide some number of the form 1 + l^{2} + m^{2}, where l and m are integers. This latter number can be factored in Hurwitz quaternions
 1 + l^{2} + m^{2} = (1 + l i + m j) (1 − l i − m j)
If p could not be factored in Hurwitz quaternions, it would be a Hurwitz prime number by definition. Then, by unique factorization, p would have to divide either 1 + l i + m j or 1 − l i − m j to form another Hurwitz quaternion. But for p>2, the number
 1/p ± l/p i ± m/p j
is not a Hurwitz integer. Therefore, every p>2 can be factored in Hurwitz quaternions, and the foursquare theorem holds.
[edit] Historical development
"[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. 
The Euclidean algorithm is the oldest algorithm in the surviving historical record. It appeared in Euclid's Elements around 300 BC, specifically in Book 7 (Propositions 1–2) and Book 10 (Propositions 2–3). In Book 7, the algorithm is formulated for integers (Book 7), whereas in Book 10, it is formulated for real numbers. The latter algorithm is geometrical; the GCD of two lengths a and b corresponds to the greatest length g that is commensurate with both.
The algorithm was probably not discovered by Euclid, who compiled many earlier results in his Elements.^{[52]}^{[53]} 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.^{[54]} The algorithm was likely known by Eudoxus of Cnidus (about 375 BC),^{[55]}^{[56]} and Aristotle (about 330 BC) hints at it in his Topics, 158b, 29–35.
Euclid's algorithm was reinvented both in India and in China,^{[57]} 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", and applied it solving linear Diophantine equations.^{[58]} Although a special case of the Chinese remainder theorem was described earlier 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 algorithm was first described in Europe in the second edition of Bachet's Problèmes plaisants et délectables (1624).^{[58]} 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 19thcentury, Carl Friedrich Gauss used the Euclidean algorithm to demonstrate unique factorization of Gaussian integers by 1815 (published 1832), although he did not mention the algorithm in his earlier work, Disquisitiones Arithmeticae (1801), except as a method for continued fractions.^{[59]} 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 in which the Euclidean algorithm could be applied.^{[60]} Dirichlet's insight likely inspired Richard Dedekind to develop theories for new types of numbers, the algebraic integers, and more generally Euclidean domains. For example, Dedekind was the first to prove Fermat's twosquare theorem using the unique factorization of Gaussian integers.^{[61]} However, through Dedekind's work, the importance of the Euclidean algorithm in number theory gradually became eclipsed by the more general theory of ideals.^{[62]}
Other applications of Euclid's algorithm were developed in the 19th century. In 1829, Sturm showed that the algorithm provided an efficient method for counting the number of real roots of polynomials in any given interval.^{[63]} A generalization of this result is known as Sturm's theorem.
The Euclidean algorithm was the first integer relation algorithm developed, that is, the first method for finding integer relations between commensurate real numbers. No new general algorithms were developed until 1979, when the FergusonForcade algorithm was developed by Helaman Ferguson and R.W. Forcade.^{[64]} Since that time, several others have been developed, such as the LLL algorithm, the HJLS algorithm, and the PSLQ algorithm. The PSLQ algorithm has been recognized as one of the top ten algorithms of the 20th century.^{[65]}
[edit] See also
 Binary GCD algorithm
 Lehmer's GCD algorithm
 Extended Euclidean algorithm
 Greatest common divisor of two polynomials
[edit] References
 ^ Stark, p. 16
 ^ Stark, p. 21.
 ^ LeVeque, p. 32.
 ^ Ore, p. 47.
 ^ Leveque, p. 31.
 ^ Schroeder, pp. 21–22.
 ^ Schroeder, p. 19.
 ^ Ogilvy CS, Anderson JT (1966). Excursions in number theory. New York: Oxford University Press. pp. 27–29. LCCN 6614484.
 ^ Schroeder, p. 22.
 ^ Lovász L, Pelikán J, Vesztergombi K (2003). Discrete Mathematics: Elementary and Beyond. New York: SpringerVerlag. pp. 100–101. ISBN 0387955844.
 ^ Knuth, p. 320.
 ^ ^{a} ^{b} Ore, p. 43.
 ^ ^{a} ^{b} Stewart BM (1964). Theory of Numbers (2nd ed.). New York: Macmillan. pp. 43–44. LCCN 6410964.
 ^ Leveque, p. 33.
 ^ Koshy T (2002). Elementary Number Theory with Applications. Burlington, MA: Harcourt/Academic Press. pp. 167–169. ISBN 0124211712.
 ^ Ore, p. 44.
 ^ Ore, p. 44.
 ^ Schroeder, pp. 106–107.
 ^ Schroeder, pp. 108–109.
 ^ Schroeder, pp. 107–109.
 ^ Stillwell, pp. 186–187.
 ^ Schroeder, p. 134.
 ^ Schroeder, pp. 194–195.
 ^ Vinogradov IM (1954). Elements of Number Theory. New York: Dover. pp. 3–13.
 ^ Lamé G (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus Acad. Sci. 19: 867–870.
 ^ LeVeque, p. 35.
 ^ Ore, p. 45.
 ^ Knuth, p. 344.
 ^ Knuth, p. 343.
 ^ Mollin, p. 21.
 ^ Knuth, p. 343.
 ^ Mollin, pp. 21–22.
 ^ Knuth, p. 344.
 ^ Knuth, p. 353.
 ^ Knuth, p. 357.
 ^ Porter JW (1975). "On a Theorem of Heilbronn". Mathematika 22: 20–28.
 ^ Knuth DE (1976). Computers and Math. with Applic. 2: 137–139.
 ^ Dixon JD (1970). "The Number of Steps in the Euclidean Algorithm". J. Number Theory 2: 414–422.
 ^ Heilbronn HA (1969). Paul Turán. ed. Number Theory and Analysis. New York: Plenum. pp. 87–96.
 ^ Knuth, p. 354.
 ^ Knuth, p. 355.
 ^ Knuth, p. 355.
 ^ Knuth, p. 356.
 ^ R. Crandall & C. Pomerance. Prime Numbers  A Computational Perspective. Second Edition, Springer 2005.
 ^ N. Möller. On Schönhage's algorithm and subquadratic integer gcd computation, preprint.
 ^ ^{a} ^{b} Lang S (1984). Algebra (2nd ed.). Menlo Park, CA: AddisonWesley. pp. 190–194. ISBN 0201054876.
 ^ Schroeder, pp. 254–259.
 ^ Gauss CF (1832). "Theoria residuorum biquadraticorum". Comm. Soc. Reg. Sci. Gött. Rec. 4.. See also Werke, 2:67–148.
 ^ Stillwell J (2003). Elements of Number Theory. New York: SpringerVerlag. pp. 101–116. ISBN 0387955879.
 ^ Cohn H (1962). Advanced Number Theory. New York: Dover. pp. 104–110. ISBN 048664023X.
 ^ Stillwell J (2003). Elements of Number Theory. New York: SpringerVerlag. pp. 151–152. ISBN 0387955879.
 ^ Weil A (1983). Number Theory. Boston: Birkhäuser. pp. 4–6. ISBN 0817631410.
 ^ Jones A (1994). "Greek mathematics to AD 300". Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. pp. 46–48. ISBN 0415092388.
 ^ van der Waerden BL (1954). Science Awakening. translated by Arnold Dresden. Groningen: P. Noordhoff Ltd.. pp. 114–115.
 ^ Knuth, p. 318.
 ^ von Fritz K (1945). Ann. Math. 46: 242–264.
 ^ Stillwell, p. 31.
 ^ ^{a} ^{b} Tattersall JJ (2005). Elementary number theory in nine chapters. Cambridge: Cambridge University Press. pp. 70. ISBN 9780521850148.
 ^ Stillwell, p. 31.
 ^ Stillwell, pp. 31–32; Dirichlet, pp. 29–31.
 ^ Dedekind R (1894). "Supplement XI". in PGL Dirichlet. Vorlesungen über Zahlentheorie.
 ^ Stillwell J (2003). Elements of Number Theory. New York: SpringerVerlag. pp. 41–42. ISBN 0387955879.
 ^ Sturm C (1829). "Mémoire sur la résolution des équations numériques". Bull. des sciences de Férussac 11.
 ^ Eric W. Weisstein, Integer Relation at MathWorld.
 ^ The Best of the 20th Century: Editors Name Top 10 Algorithms by Barry A. Cipra; SIAM News, Volume 33, Number 4
[edit] Bibliography
 Cormen TH, Leiserson CE, Rivest RL, and Stein C (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw–Hill. pp. 856–862 (Section 31.2). ISBN 0262032937.
 Cox D, Little J, and O'Shea D (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (2nd ed.). SpringerVerlag. pp. 29–46 (Chapter 1). ISBN 0387946802.
 Dirichlet PGL (1894). Richard Dedekind. ed. Vorlesungen über Zahlentheorie. Braunschweig: Vieweg.
 Hardy GH, Wright EM (1954). An Introduction to the Theory of Numbers (3rd ed.). Oxford: Clarendon Press. pp. 178–189.
 Kimberling C (1983). "A Visual Euclidean Algorithm". Mathematics Teacher 76: 108–109.
 Knuth D (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). AddisonWesley. pp. 333–379 (Sections 4.5.2–4.5.3). ISBN 0201896842.
 LeVeque WJ (1977). Fundamentals of Number Theory. New York: Dover. pp. 31–46. ISBN 0486689069.
 Mollin RA (2008). Fundamental Number Theory with Applications (2nd ed.). Boca Raton: Chapman & Hall/CRC. pp. 16–29. ISBN 9781420066593.
 Ore Ø (1948). Number Theory and Its History. New York: McGrawHill.
 Schroeder MR. Number Theory in Science and Communication (4th ed.). SpringerVerlag. pp. Chap. 2, pp. 17–25; Chap. 5, pp. 55–56, 81–86; Chap. 6, 87–98; Chap. 16, pp. 186–188; Chap. 24, pp. 253–258. ISBN 0387158006.
 Stark H (1978). An Introduction to Number Theory. MIT Press. pp. 16–33, 44–50 (Chap. 2); 145–163 (Chap. 5); 257–299 (Chap. 8). ISBN 0262690608.
 Stillwell J (1997). Numbers and Geometry. New York: SpringerVerlag. pp. 13–21, 30–32, 186–187, 230–233, 267–271. ISBN 0387982892.
 Uspensky JV, Heaslet MA (1939). Elementary Number Theory. New York: McGrawHill.
[edit] External links
 Euclid's Algorithm at cuttheknot
 Binary Euclid's Algorithm (Java) at cuttheknot
 Euclid's Game (Java) at cuttheknot
 Eric W. Weisstein, Euclidean Algorithm at MathWorld.
 Eric W. Weisstein, Lamé's Theorem at MathWorld.
 Euclid's algorithm at PlanetMath.
 Music and Euclid's algorithm
 The Euclidean Algorithm at MathPages
 An animated implementation with arbitrary precision integer arithmetic
 Implementation in Javascript
