Euclidean algorithm

The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers and . The greatest common divisor is the largest natural number that divides both and without leaving a remainder. Synonyms for GCD include greatest common factor (GCF), highest common factor (HCF), highest common divisor (HCD), and greatest common measure (GCM). The greatest common divisor is often written as or, more simply, as , although the latter notation is ambiguous, also used for concepts such as an ideal in the ring of integers, which is closely related to GCD. If , then and are said to be coprime (or relatively prime). This property does not imply that or are themselves prime numbers. For example, and factor as and , so they are not prime, but their prime factors are different, so and are coprime, with no common factors other than . Let . Since and are both multiples of , they can be written and , and there is no larger number for which this is true. The natural numbers and must be coprime, since any common factor could be factored out of and to make greater. Thus, any other number that divides both and must also divide . The greatest common divisor of and is the unique (positive) common divisor of and that is divisible by any other common divisor . The greatest common divisor can be visualized as follows. Consider a rectangular area by , and any common divisor that divides both and exactly. The sides of the rectangle can be divided into segments of length , which divides the rectangle into a grid of squares of side length . The GCD is the largest value of for which this is possible. For illustration, a rectangular area can be divided into a grid of: squares, squares, squares, squares, squares or squares. Therefore, is the GCD of and . A rectangular area can be divided into a grid of squares, with two squares along one edge () and five squares along the other (). The greatest common divisor of two numbers and is the product of the prime factors shared by the two numbers, where each prime factor can be repeated as many times as it divides both and . For example, since can be factored into , and can be factored into , the GCD of and equals , the product of their shared prime factors (with 3 repeated since divides both). If two numbers have no common prime factors, their GCD is (obtained here as an instance of the empty product); in other words, they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors. Factorization of large integers is believed to be a computationally very difficult problem, and the security of many widely used cryptographic protocols is based upon its infeasibility. Another definition of the GCD is helpful in advanced mathematics, particularly ring theory. but it can also be calculated by repeatedly taking the GCDs of pairs of numbers. For example, : Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers. == Description ==

Procedure The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers r_{-2} = a and r_{-1} = b and will eventually terminate with the integer zero: \{ r_{-2} = a,\ r_{-1} = b,\ r_0,\ r_1,\ \cdots,\ r_{n-1},\ r_n = 0 \} with r_{k+1} The integer r_{n-1} will then be the GCD and we can state \text{gcd}(a,b) = r_{n-1}. The algorithm indicates how to construct the intermediate remainders r_k via division-with-remainder on the preceding pair (r_{k-2},\ r_{k-1}) by finding an integer quotient q_k so that: : r_{k-2} = q_k \cdot r_{k-1} + r_k \text{, with } \ r_{k-1} > r_k \geq 0. Because the sequence of non-negative integers \{ r_k \} is strictly decreasing, it eventually must terminate. In other words, since r_k \ge 0 for every k, and each r_k is an integer that is strictly smaller than the preceding r_{k-1}, there eventually cannot be a non-negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the th step with r_n equal to zero. To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially \{r_{-2} = 1071,\ r_{-1} = 462 \} and in order to find r_0, we need to find integers q_0 and r_0 such that: : 1071 = q_0 \cdot 462 + r_0. This is the quotient q_0 = 2 since 1071 = 2 \cdot 462 + 147. This determines r_0 = 147 and so the sequence is now \{1071,\ 462,\ r_0 = 147 \}. The next step is to continue the sequence to find r_1 by finding integers q_1 and r_1 such that: : 462 = q_1 \cdot 147 + r_1. This is the quotient q_1 = 3 since 462 = 3 \cdot 147 + 21. This determines r_1 = 21 and so the sequence is now \{1071,\ 462,\ 147,\ r_1 = 21 \}. The next step is to continue the sequence to find r_2 by finding integers q_2 and r_2 such that: : 147 = q_2 \cdot 21 + r_2. This is the quotient q_2 = 7 since 147 = 7 \cdot 21 + 0. This determines r_2 = 0 and so the sequence is completed as \{1071,\ 462,\ 147,\ 21,\ r_2 = 0 \} as no further non-negative integer smaller than 0 can be found. The penultimate remainder 21 is therefore the requested GCD: : \text{gcd}(1071,\ 462) = 21. We can generalize slightly by dropping any ordering requirement on the initial two values a and b. If a = b, the algorithm may continue and trivially find that \text{gcd}(a,\ a) = a as the sequence of remainders will be \{a,\ a,\ 0\}. If a then we can also continue since a \equiv 0 \cdot b + a, suggesting the next remainder should be a itself, and the sequence is \{a,\ b,\ a,\ \cdots \}. Normally, this would be invalid because it breaks the requirement r_0 but now we have a by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy r_0 and everything continues as above. The only modifications that need to be made are that r_{k} only for k \ge 0, and that the sub-sequence of non-negative integers \{ r_{k-1} \} for k \ge 0 is strictly decreasing, therefore excluding a = r_{-2} from both statements. 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 is shown to divide both and . Since it is a common divisor, it must be less than or equal to the greatest common divisor . In the second step, it is shown that any common divisor of and , including , must divide ; therefore, must be less than or equal to . These two opposite inequalities imply . To demonstrate that divides both and (the first step), divides its predecessor : since the final remainder is zero. also divides its next predecessor : because it divides both terms on the right-hand side of the equation. Iterating the same argument, divides all the preceding remainders, including and . None of the preceding remainders , , etc. divide and , since they leave a remainder. Since is a common divisor of and , . In the second step, any natural number that divides both and (in other words, any common divisor of and ) divides the remainders . By definition, and can be written as multiples of : and , where and are natural numbers. Therefore, divides the initial remainder , since . An analogous argument shows that also divides the subsequent remainders , , etc. Therefore, the greatest common divisor must divide , which implies that . Since the first part of the argument showed the reverse (), it follows that . Thus, is the greatest common divisor of all the succeeding pairs: : g = \gcd(a, b) = \gcd(a, r_0) = \gcd(r_0, r_1) = \dots = \gcd(r_{k-1}, r_{k}) = \dots = \gcd(r_{N-2}, r_{N-1}) = \gcd(r_{N-1}, 0) = r_{N-1} Worked example For illustration, the Euclidean algorithm can be used to find the greatest common divisor of and . To begin, multiples of are subtracted from until the remainder is less than . Two such multiples can be subtracted (), leaving a remainder of : : . Then multiples of are subtracted from until the remainder is less than . Three multiples can be subtracted (), leaving a remainder of : : . Then multiples of are subtracted from until the remainder is less than . Seven multiples can be subtracted (), leaving no remainder: : . Since the last remainder is zero, the algorithm ends with as the greatest common divisor of and . This agrees with the found by prime factorization above. In tabular form, the steps are: Visualization The Euclidean algorithm can be visualized in terms of the tiling analogy given above for the greatest common divisor. Assume that we wish to cover an rectangle with square tiles exactly, where is the larger of the two numbers. We first attempt to tile the rectangle using square tiles; however, this leaves an residual rectangle untiled, where . We then attempt to tile the residual rectangle with square tiles. This leaves a second residual rectangle , which we attempt to tile using 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 (shown in red), and is the GCD of and , the dimensions of the original rectangle (shown in green). Euclidean division At every step , the Euclidean algorithm computes a quotient and remainder from two numbers and : , where the is non-negative and is strictly less than the absolute value of . The theorem which underlies the definition of the Euclidean division ensures that such a quotient and remainder always exist and are unique. In Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is, is subtracted from repeatedly until the remainder is smaller than . After that and are exchanged and the process is iterated. Euclidean division reduces all the steps between two exchanges into a single step, which is thus more efficient. Moreover, the quotients are not needed, thus one may replace Euclidean division by the modulo operation, which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply : . 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 th iteration, the variable holds the latest remainder , whereas the variable holds its predecessor, . The step is equivalent to the above recursion formula . The temporary variable holds the value of while the next remainder is being calculated. At the end of the loop iteration, the variable holds the remainder , whereas the variable holds its predecessor, . (If negative inputs are allowed, or if the mod function may return negative values, the last line must be replaced with .) In the subtraction-based version, which was Euclid's original version, the remainder calculation () is replaced by repeated subtraction. Contrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops when : function gcd(a, b) while a ≠ b if a > b a := a − b else b := b − a return a The variables and alternate holding the previous remainders and . Assume that is larger than at the beginning of an iteration; then equals , since . During the loop iteration, is reduced by multiples of the previous remainder until is smaller than . Then is the next remainder . Then is reduced by multiples of until it is again smaller than , giving the next remainder , and so on. The recursive version is based on the equality of the GCDs of successive remainders and the stopping condition . function gcd(a, b) if b = 0 return a else return gcd(b, a mod b) (As above, if negative inputs are allowed, or if the mod function may return negative values, the instruction must be replaced by .) For illustration, the is calculated from the equivalent . The latter GCD is calculated from the , which in turn is calculated from the . Method of least absolute remainders In another version of Euclid's algorithm, the quotient at each step is increased by one if the resulting negative remainder is smaller in magnitude than the typical positive remainder. Previously, the equation : assumed that . However, an alternative negative remainder can be computed: : if or : if . If is replaced by . when , then one gets a variant of Euclidean algorithm such that : at each step. Leopold Kronecker has shown that this version requires the fewest steps of any version of Euclid's algorithm. == Historical development ==

, depicted here holding a compass in a painting of about 1474. The Euclidean algorithm is one of the oldest algorithms 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; the concept of real numbers was unknown at that time.) The latter algorithm is geometrical. The GCD of two lengths and corresponds to the greatest length that measures and evenly; in other words, the lengths and are both integer multiples of the length . 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. Claude Brezinski, following remarks by Pappus of Alexandria, credits the algorithm to Theaetetus (c. 417 – c. 369 BC). Centuries later, Euclid's algorithm was discovered independently both in India and in China, primarily to solve Diophantine equations that arose in astronomy and making accurate calendars. In the late 5th 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 in the Chinese book Sunzi Suanjing, 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 numerically and popularized in Europe in the second edition of Bachet's Problèmes plaisants et délectables (Pleasant and enjoyable problems, 1624). 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. Lejeune Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied. Lejeune Dirichlet's lectures on number theory were edited and extended by Richard Dedekind, 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, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of ideals. 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, such as the algorithm of Helaman Ferguson and R.W. Forcade (1979) and the LLL algorithm. In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called The Game of Euclid, which has an optimal strategy. The players begin with two piles of and stones. The players take turns removing multiples of the smaller pile from the larger. Thus, if the two piles consist of and stones, where is larger than , the next player can reduce the larger pile from stones to 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 of two integers and can be represented as a linear sum of the original two numbers and . In other words, it is always possible to find integers and such that . The integers and can be calculated from the quotients , , etc. by reversing the order of equations in Euclid's algorithm. Beginning with the next-to-last equation, can be expressed in terms of the quotient and the two preceding remainders, and : : . Those two remainders can be likewise expressed in terms of their quotients and preceding remainders, : and : . Substituting these formulae for and into the first equation yields as a linear sum of the remainders and . The process of substituting remainders by formulae involving their predecessors can be continued until the original numbers and are reached: : : : . After all the remainders , , etc. have been substituted, the final equation expresses as a linear sum of and , so that . The Euclidean algorithm, and thus Bézout's identity, can 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 of two numbers and . Consider the set of all numbers , where and are any two integers. Since and are both divisible by , every number in the set is divisible by . In other words, every number of the set is an integer multiple of . This is true for every common divisor of and . However, unlike other common divisors, the greatest common divisor is a member of the set; by Bézout's identity, choosing and gives . A smaller common divisor cannot be a member of the set, since every member of the set must be divisible by . Conversely, any multiple of can be obtained by choosing and , where and are the integers of Bézout's identity. This may be seen by multiplying Bézout's identity by m, : . Therefore, the set of all numbers is equivalent to the set of multiples of . In other words, the set of all possible sums of integer multiples of two numbers ( and ) is equivalent to the set of multiples of . The GCD is said to be the generator of the ideal of and . 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 and . By adding/subtracting multiples of the first cup and multiples of the second cup, any volume can be measured out. These volumes are all multiples of . Extended Euclidean algorithm The integers and of Bézout's identity can be computed efficiently using the extended Euclidean algorithm. This extension adds two recursive equations to Euclid's algorithm : : with the starting values : : . Using this recursion, Bézout's integers and are given by and , where is the step on which the algorithm terminates with . The validity of this approach can be shown by induction. Assume that the recursion formula is correct up to step of the algorithm; in other words, assume that : for all less than . The th step of the algorithm gives the equation : . Since the recursion formula has been assumed to be correct for and , they may be expressed in terms of the corresponding and variables : . Rearranging this equation yields the recursion formula for step , as required : . Matrix method The integers and can also be found using an equivalent matrix method. The sequence of equations of Euclid's algorithm : \begin{align} a & = q_0 b + r_0 \\ b & = q_1 r_0 + r_1 \\ & \,\,\,\vdots \\ r_{N-2} & = q_N r_{N-1} + 0 \end{align} can be written as a product of 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 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 as a linear sum of and , both sides of this equation can be multiplied by the inverse of the matrix . The determinant of equals , since it equals the product of the determinants of the quotient matrices, each of which is negative one. Since the determinant of is never zero, the vector of the final remainders can be solved using the inverse of --> : \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 : , the two integers of Bézout's identity are and . 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 can be written as a product of two factors and , that is, . If another number also divides but is coprime with , then must divide , by the following argument: If the greatest common divisor of and is , then integers and can be found such that : by Bézout's identity. Multiplying both sides by gives the relation: : Since divides both terms on the right-hand side, it must also divide the left-hand side, . This result is known as Euclid's lemma. Specifically, if a prime number divides , then it must divide at least one factor of . Conversely, if a number is coprime to each of a series of numbers , , ..., , then is also coprime to their product, . To see this, assume the contrary, that there are two independent factorizations of into and prime factors, respectively : . Since each prime divides by assumption, it must also divide one of the factors; since each is prime as well, it must be that . Iteratively dividing by the factors shows that each has an equal counterpart ; 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 , . The solutions are shown as blue circles. Diophantine equations are equations in which the solutions are restricted to integers; they are named after the 3rd-century Alexandrian mathematician Diophantus. A typical linear Diophantine equation seeks integers and such that : where , and are given integers. This can be written as an equation for in modular arithmetic: : . Let be the greatest common divisor of and . Both terms in are divisible by ; therefore, must also be divisible by , or the equation has no solutions. By dividing both sides by , the equation can be reduced to Bezout's identity : , where and can be found by the extended Euclidean algorithm. This provides one solution to the Diophantine equation, and . In general, a linear Diophantine equation has no solutions, or an infinite number of solutions. To find the latter, consider two solutions, and , where : or equivalently : . Therefore, the smallest difference between two solutions is , whereas the smallest difference between two solutions is . Thus, the solutions may be expressed as : : . By allowing to vary over all possible integers, an infinite family of solutions can be generated from a single solution . If the solutions are required to be positive integers , only a finite number of solutions may be possible. This restriction on the acceptable solutions allows some systems of Diophantine equations with more unknowns than equations to have a finite number of solutions; this is impossible for a system of linear equations when the solutions can be any real number (see Underdetermined system). 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 using modular arithmetic. In this field, the results of any mathematical operation (addition, subtraction, multiplication, or division) is reduced modulo ; that is, multiples of are added or subtracted until the result is brought within the range –. For example, the result of . Such finite fields can be defined for any prime ; using more sophisticated definitions, they can also be defined for any power of a prime . Finite fields are often called Galois fields, and are abbreviated as or ). In such a field with numbers, every nonzero element has a unique modular multiplicative inverse, such that . This inverse can be found by solving the congruence equation , or the equivalent linear Diophantine equation : . This equation can be solved by the Euclidean algorithm, as described above. Finding multiplicative inverses is an essential step in the RSA algorithm, which is widely used in electronic commerce; specifically, the equation determines the integer used to decrypt the message. 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 xi modulo a set of N coprime numbers mi: : \begin{align} x_1 & \equiv x \pmod {m_1} \\ x_2 & \equiv x \pmod {m_2} \\ & \,\,\,\vdots \\ x_N & \equiv x \pmod {m_N} \,. \end{align} The goal is to determine x from its N remainders xi. 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 mi, and define Mi as : M_i = \frac M {m_i}. Thus, each Mi is the product of all the moduli except mi. The solution depends on finding N new numbers hi such that : M_i h_i \equiv 1 \pmod {m_i} \,. With these numbers hi, any integer x can be reconstructed from its remainders xi by the equation : x \equiv (x_1 M_1 h_1 + x_2 M_2 h_2 + \cdots + x_N M_N h_N) \pmod M \,. Since these numbers hi are the multiplicative inverses of the Mi, they may be found using Euclid's algorithm as described in the previous subsection. Stern–Brocot tree The Euclidean algorithm can be used to arrange the set of all positive rational numbers into an infinite binary search tree, called the Stern–Brocot tree. The number 1 (expressed as a fraction 1/1) is placed at the root of the tree, and the location of any other number a/b can be found by computing gcd(a,b) using the original form of the Euclidean algorithm, in which each step replaces the larger of the two given numbers by its difference with the smaller number (not its remainder), stopping when two equal numbers are reached. A step of the Euclidean algorithm that replaces the first of the two numbers corresponds to a step in the tree from a node to its right child, and a step that replaces the second of the two numbers corresponds to a step in the tree from a node to its left child. The sequence of steps constructed in this way does not depend on whether a/b is given in lowest terms, and forms a path from the root to a node containing the number a/b. This fact can be used to prove that each positive rational number appears exactly once in this tree. For example, 3/4 can be found by starting at the root, going to the left once, then to the right twice: : \begin{align} & \gcd(3,4) & \leftarrow \\ = {} & \gcd(3,1) & \rightarrow \\ = {} & \gcd(2,1) & \rightarrow \\ = {} & \gcd(1,1). \end{align} The Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called the Calkin–Wilf tree. The difference is that the path is reversed: instead of producing a path from the root of the tree to a target, it produces a path from the target to the root. Continued fractions The Euclidean algorithm has a close relationship with continued fractions. The sequence of equations can be written in the form : \begin{align} \frac a b &= q_0 + \frac{r_0} b \\ \frac b {r_0} &= q_1 + \frac{r_1}{r_0} \\ \frac{r_0}{r_1} &= q_2 + \frac{r_2}{r_1} \\ & \,\,\, \vdots \\ \frac{r_{k-2}}{r_{k-1}} &= q_k + \frac{r_k}{r_{k-1}} \\ & \,\,\, \vdots \\ \frac{r_{N-2}}{r_{N-1}} &= q_N\,. \end{align} The last term on the right-hand side always equals the inverse of the left-hand side of the next equation. Thus, the first two equations may be combined to form : \frac a b = q_0 + \cfrac 1 {q_1 + \cfrac{r_1}{r_0}} \,. The third equation may be used to substitute the denominator term r1/r0, yielding : \frac a b = q_0 + \cfrac 1 {q_1 + \cfrac 1 {q_2 + \cfrac{r_2}{r_1}}}\,. The final ratio of remainders rk/rk−1 can always be replaced using the next equation in the series, up to the final equation. The result is a continued fraction : \frac a b = q_0 + \cfrac 1 {q_1 + \cfrac 1 {q_2 + \cfrac{1}{\ddots + \cfrac 1 {q_N}}}} = [ q_0; q_1, q_2, \ldots , q_N ] \,. In the worked example above, the gcd(1071, 462) was calculated, and the quotients qk were 2, 3 and 7, respectively. Therefore, the fraction 1071/462 may be written : \frac{1071}{462} = 2 + \cfrac 1 {3 + \cfrac 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 ==

. The computational efficiency of Euclid's algorithm has been studied thoroughly. This efficiency can be described by the number of division steps the algorithm requires, multiplied by the computational expense of each step. The first known analysis of Euclid's algorithm is due to A. A. L. Reynaud in 1811, who showed that the number of division steps on input (u, v) is bounded by v; later he improved this to v/2 + 2. Later, in 1841, P. J. E. Finck showed that the number of division steps is at most 2 log2 v + 1, and hence Euclid's algorithm runs in time polynomial in the size of the input. Émile Léger, in 1837, studied the worst case, which is when the inputs are consecutive Fibonacci numbers. Finck's analysis was refined by Gabriel Lamé in 1844, who showed that the number of steps required for completion is never more than five times the number h of base-10 digits of the smaller number b. In the uniform cost model (suitable for analyzing the complexity of gcd calculation on numbers that fit into a single machine word), each step of the algorithm takes constant time, and Lamé's analysis implies that the total running time is also O(h). However, in a model of computation suitable for computation with larger numbers, the computational expense of a single remainder computation in the algorithm can be as large as O(h2). If g is the GCD of a and b, then a = mg and b = ng for two coprime numbers m and n. Then : as may be seen by dividing all the steps in the Euclidean algorithm by g. By the same argument, the number of steps remains the same if a and b are multiplied by a common factor w: T(a, b) = T(wa, wb). Therefore, the number of steps T may vary dramatically between neighboring pairs of numbers, such as T(a, b) and T(a, b + 1), depending on the size of the two GCDs. The recursive nature of the Euclidean algorithm gives another equation : where T(x, 0) = 0 by assumption. More precisely, if the Euclidean algorithm requires N steps for the pair a > b, then one has a ≥ FN+2 and b ≥ FN+1. 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 F2 and F3, 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 = q0b + r0, and the Euclidean algorithm requires M − 1 steps for the pair b > r0. By induction hypothesis, one has b ≥ FM+1 and r0 ≥ FM. Therefore, a = q0b + r0 ≥ b + r0 ≥ FM+1 + FM = FM+2, which is the desired inequality. 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. For if the algorithm requires N steps, then b is greater than or equal to FN+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 log10φ > 1/5, (N − 1)/5 10φ logφb = log10b. Thus, N ≤ 5 log10b. Thus, the Euclidean algorithm always needs less than O(h) divisions, where h is the number of digits in the smaller number b. Average The average number of steps taken by the Euclidean algorithm has been defined in three different ways. The first definition is the average time T(a) required to calculate the GCD of a given number a and a smaller natural number b chosen with equal probability from the integers 0 to a − 1 To reduce this noise, a second average τ(a) is taken over all numbers coprime with a --> : \tau(a) = \frac 1 {\varphi(a)} \sum_{\begin{smallmatrix} 0 \leq b There are φ(a) coprime integers less than a, where φ is Euler's totient function. This tau average grows smoothly with a :\tau(a) = \frac{12}{\pi^2}\ln 2 \ln a + C + O(a^{-1/6-\varepsilon}) with the residual error being of order a−(1/6)+ε, where ε is infinitesimal. The constant C in this formula is called Porter's constant and equals : C= -\frac 1 2 + \frac{6 \ln 2}{\pi^2}\left(4\gamma -\frac{24}{\pi^2}\zeta'(2) + 3\ln 2 - 2\right) \approx 1.467 where is the Euler–Mascheroni constant and is the derivative of the Riemann zeta function. The leading coefficient (12/π2) ln 2 was determined by two independent methods. Since the first average can be calculated from the tau average by summing over the divisors d of a --> : T(a) = \frac 1 a \sum_{d \mid a} \varphi(d) \tau(d) it can be approximated by the formula : T(a) \approx C + \frac{12}{\pi^2} \ln 2\, \biggl({\ln a} - \sum_{d \mid a} \frac{\Lambda(d)} d\biggr) 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) \approx \frac{12}{\pi^2} \ln 2 \ln n + 0.06. Computational expense per step In each step k of the Euclidean algorithm, the quotient qk and remainder rk are computed for a given pair of integers rk−2 and rk−1 : The computational expense per step is associated chiefly with finding qk, since the remainder rk can be calculated quickly from rk−2, rk−1, and qk : The computational expense of dividing h-bit numbers scales as , 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 where . 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 (h2) with the average number of digits h in the initial two numbers a and b. Let represent the number of digits in the successive remainders . Since the number of steps N grows linearly with h, the running time is bounded by --> : O\Big(\sum_{i 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. However, this alternative also scales like O(h²). It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way. Additional efficiency can be gleaned by examining only the leading digits of the two numbers a and b. The binary algorithm can be extended to other bases (k-ary algorithms), with up to fivefold increases in speed. Lehmer's GCD algorithm uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases. A recursive approach for very large integers (with more than 25,000 digits) leads to quasilinear 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 quasilinear methods generally scale as == Generalizations ==

Although the Euclidean algorithm is used to find the greatest common divisor of two natural numbers (positive integers), it may be generalized to the real numbers, and to other mathematical objects, such as polynomials, The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders are real numbers, although the quotients are integers as before. Second, the algorithm is not guaranteed to end in a finite number of steps. If it does, the fraction is a rational number, i.e., the ratio of two integers : \frac{a}{b} = \frac{mg}{ng} = \frac{m}{n}, and can be written as a finite continued fraction . If the algorithm does not stop, the fraction is an irrational number and can be described by an infinite continued fraction . Examples of infinite continued fractions are the golden ratio and the square root of two, . When applied to two arbitrary real numbers, the algorithm is unlikely to stop, since almost all ratios of two real numbers are irrational. An infinite continued fraction may be truncated at a step to yield an approximation to that improves as is increased. The approximation is described by convergents ; the numerator and denominators are coprime and obey the recurrence relation : \begin{align} m_k &= q_k m_{k-1} + m_{k-2} \\ n_k &= q_k n_{k-1} + n_{k-2}, \end{align} where and are the initial values of the recursion. The convergent is the best rational number approximation to with denominator : : \left|\frac{a}{b} - \frac{m_k}{n_k}\right| Polynomials Polynomials in a single variable x can be added, multiplied and factored into irreducible polynomials, which are the analogs of the prime numbers for integers. The greatest common divisor polynomial of two polynomials and is defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm. The basic procedure is similar to that for integers. At each step , a quotient polynomial and a remainder polynomial are identified to satisfy the recursive equation : r_{k-2}(x) = q_k(x)r_{k-1}(x) + r_k(x), where and . Each quotient polynomial is chosen such that each remainder is either zero or has a degree that is smaller than the degree of its predecessor: . Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps. The last nonzero remainder is the greatest common divisor of the original two polynomials, and . For example, consider the following two quartic polynomials, which each factor into two quadratic polynomials : \begin{align} a(x) &= x^4 - 4x^3 + 4x^2 - 3x + 14 = (x^2 - 5x + 7)(x^2 + x + 2) \qquad \text{and}\\ b(x) &= x^4 + 8x^3 + 12x^2 + 17x + 6 = (x^2 + 7x + 3)(x^2 + x + 2). \end{align} Dividing by yields a remainder . In the next step, is divided by yielding a remainder . Finally, dividing by yields a zero remainder, indicating that is the greatest common divisor polynomial of and , consistent with their factorization. Many of the applications described above for integers carry over to polynomials. The Euclidean algorithm can be used to solve linear Diophantine equations and Chinese remainder problems for polynomials; continued fractions of polynomials can also be defined. The polynomial Euclidean algorithm has other applications, such as Sturm chains, a method for counting the zeros of a polynomial that lie inside a given real interval. This in turn has applications in several areas, such as the Routh–Hurwitz stability criterion in control theory. Finally, the coefficients of the polynomials need not be drawn from integers, real numbers or even the complex numbers. For example, the coefficients may be drawn from a general field, such as the finite fields described above. The corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials. and is the square root of negative one. This unique factorization is helpful in many applications, such as deriving all Pythagorean triples or proving Fermat's theorem on sums of two squares. In general, the Euclidean algorithm is convenient in such applications, but not essential; for example, the theorems can often be proven by other arguments. The Euclidean algorithm developed for two Gaussian integers and is nearly the same as that for ordinary integers, but differs in two respects. As before, we set and , and the task at each step is to identify a quotient and a remainder such that : r_k = r_{k-2} - q_k r_{k-1}, where every remainder is strictly smaller than its predecessor: . The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are complex numbers. The quotients are generally found by rounding the real and complex parts of the exact ratio (such as the complex number ) to the nearest integers. The final nonzero remainder is , the Gaussian integer of largest norm that divides both and ; it is unique up to multiplication by a unit, or . Many of the other applications of the Euclidean algorithm carry over to Gaussian integers. For example, it can be used to solve linear Diophantine equations and Chinese remainder problems for Gaussian integers; continued fractions of Gaussian integers can also be defined. 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 from into the set of nonnegative integers such that, for any two nonzero elements and in , there exist and in such that and . Examples of such mappings are the absolute value for integers, the degree for univariate polynomials, and the norm for Gaussian integers above. The basic principle is that each step of the algorithm reduces f inexorably; hence, if can be reduced only a finite number of times, the algorithm must stop in a finite number of steps. This principle relies on the well-ordering property of the non-negative integers, which asserts that every non-empty set of non-negative integers has a smallest member. The fundamental theorem of arithmetic applies to any Euclidean domain: Any number from a Euclidean domain can be factored uniquely into irreducible elements. Any Euclidean domain is a unique factorization domain (UFD), although the converse is not true. In other words, a greatest common divisor may exist (for all pairs of elements in a domain), although it may not be possible to find it using a Euclidean algorithm. A Euclidean domain is always a principal ideal domain (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. Lamé's approach required the unique factorization of numbers of the form , where and are integers, and is an th root of 1, that is, . Although this approach succeeds for some values of (such as , the Eisenstein integers), in general such numbers do factor uniquely. This failure of unique factorization in some cyclotomic fields led Ernst Kummer to the concept of ideal numbers and, later, Richard Dedekind to ideals. Unique factorization of quadratic integers . The quadratic integer rings are helpful to illustrate Euclidean domains. Quadratic integers are generalizations of the Gaussian integers in which the imaginary unit i is replaced by a number . Thus, they have the form , where and are integers and has one of two forms, depending on a parameter . If does not equal a multiple of four plus one, then : \omega = \sqrt D . If, however, does equal a multiple of four plus one, then : \omega = \frac{1 + \sqrt{D}}{2} . If the function corresponds to a norm function, such as that used to order the Gaussian integers above, then the domain is known as norm-Euclidean. The norm-Euclidean rings of quadratic integers are exactly those where is one of the values −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, or 73. The cases and yield the Gaussian integers and Eisenstein integers, respectively. If is allowed to be any Euclidean function, then the list of possible values of for which the domain is Euclidean is not yet known. The first example of a Euclidean domain that was not norm-Euclidean (with ) was published in 1994. Noncommutative rings The Euclidean algorithm may be applied to some noncommutative rings such as the set of Hurwitz quaternions. Let and represent two elements from such a ring. They have a common right divisor if and for some choice of and in the ring. Similarly, they have a common left divisor if and for some choice of and in the ring. Since multiplication is not commutative, there are two versions of the Euclidean algorithm, one for right divisors and one for left divisors. Many results for the GCD carry over to noncommutative numbers. For example, Bézout's identity states that the right can be expressed as a linear combination of and . In other words, there are numbers and such that : \Gamma_\text{right} = \sigma\alpha + \tau\beta. The analogous identity for the left GCD is nearly the same: : \Gamma_\text{left} = \alpha\sigma + \beta\tau. Bézout's identity can be used to solve Diophantine equations. For instance, one of the standard proofs of Lagrange's four-square theorem, that every positive integer can be represented as a sum of four squares, is based on quaternion GCDs in this way. == See also ==