{"history":[],"article":{"id":"a5c8b9c9-5cb4-4ff2-ad8a-bd20e40eb32c","title":"Euclidean algorithm","slug":"euclidean-algorithm","content":":::summary\n:::\n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), the **Euclidean algorithm**, or **Euclid's algorithm**, is an efficient method for computing the [greatest common divisor](https://bliptext.com/articles/greatest-common-divisor) (GCD) of two [integers](https://bliptext.com/articles/integers), the largest number that divides them both without a [remainder](https://bliptext.com/articles/remainder).\nIt is named after the ancient Greek [mathematician](https://bliptext.com/articles/mathematician) [Euclid](https://bliptext.com/articles/euclid), who first described it in his Elements (c. 300 BC).\nIt is an example of an [algorithm](https://bliptext.com/articles/algorithm), a step-by-step procedure for performing a calculation according to well-defined rules,\nand is one of the oldest algorithms in common use.\nIt can be used to reduce [fractions](https://bliptext.com/articles/fraction-mathematics) to their [simplest form](https://bliptext.com/articles/irreducible-fraction), and is a part of many other number-theoretic and cryptographic calculations.\nThe Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.\nFor example, 21 is the GCD of 252 and 105 (as\nand\n, and the same number 21 is also the GCD of 105 and\n252 − 105 = 147\n. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal.\nWhen that occurs, that number is the GCD of the original two numbers.\nBy [reversing the steps](https://bliptext.com/articles/) or using the [extended Euclidean algorithm](https://bliptext.com/articles/extended-euclidean-algorithm), the GCD can be expressed as a [linear combination](https://bliptext.com/articles/linear-combination) of the two original numbers, that is the sum of the two numbers, each multiplied by an [integer](https://bliptext.com/articles/integer) (for example,\n). The fact that the GCD can always be expressed in this way is known as [Bézout's identity](https://bliptext.com/articles/b-zout-s-identity).\nThe version of the Euclidean algorithm described above—which follows Euclid's original presentation—can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other.\nA more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder).\nWith this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer.\nThis was proven by [Gabriel Lamé](https://bliptext.com/articles/gabriel-lam) in 1844 ([Lamé's Theorem](https://bliptext.com/articles/lam-s-theorem)), and marks the beginning of [computational complexity theory](https://bliptext.com/articles/computational-complexity-theory).\nAdditional methods for improving the algorithm's efficiency were developed in the 20th century.\nThe Euclidean algorithm has many theoretical and practical applications.\nIt is used for reducing [fractions](https://bliptext.com/articles/fraction-mathematics) to their [simplest form](https://bliptext.com/articles/irreducible-fraction) and for performing [division](https://bliptext.com/articles/division-mathematics) in [modular arithmetic](https://bliptext.com/articles/modular-arithmetic).\nComputations using this algorithm form part of the [cryptographic protocols](https://bliptext.com/articles/cryptographic-protocol) that are used to secure [internet](https://bliptext.com/articles/internet) communications, and in methods for breaking these cryptosystems by [factoring large composite numbers](https://bliptext.com/articles/integer-factorization).\nThe Euclidean algorithm may be used to solve [Diophantine equations](https://bliptext.com/articles/diophantine-equation), such as finding numbers that satisfy multiple congruences according to the [Chinese remainder theorem](https://bliptext.com/articles/chinese-remainder-theorem), to construct [continued fractions](https://bliptext.com/articles/simple-continued-fraction), and to find accurate [rational approximations](https://bliptext.com/articles/diophantine-approximation) to real numbers.\nFinally, it can be used as a basic tool for proving theorems in [number theory](https://bliptext.com/articles/number-theory) such as [Lagrange's four-square theorem](https://bliptext.com/articles/lagrange-s-four-square-theorem) and the [uniqueness of prime factorizations](https://bliptext.com/articles/fundamental-theorem-of-arithmetic).\nThe original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as [Gaussian integers](https://bliptext.com/articles/gaussian-integer) and [polynomials](https://bliptext.com/articles/polynomial) of one variable.\nThis led to modern [abstract algebraic](https://bliptext.com/articles/abstract-algebra) notions such as [Euclidean domains](https://bliptext.com/articles/euclidean-domain).\n# [Euclid's method for finding the greatest common divisor (GCD) of two starting lengths BA and DC, both defined to be multiples of a common \"unit\" length. The length DC being shorter, it is used to \"measure\" BA, but only once because the remainder EA is less than DC. EA now measures (twice) the shorter length DC, with remainder FC shorter than EA. Then FC measures (three times) length EA. Because there is no remainder, the process ends with FC being the GCD. On the right Nicomachus's example with numbers 49 and 21 resulting in their GCD of 7 (derived from Heath 1908:300). | upload.wikimedia.org/wikipedia/commons/e/e4////Euclid%27s///algorithm///Book///VII///Proposition///2///3.svg]\n\n# Background: greatest common divisor\nThe Euclidean algorithm calculates the greatest common divisor (GCD) of two [natural numbers](https://bliptext.com/articles/natural-number) a and b. The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder.\nSynonyms for GCD include greatest common factor (GCF), highest common factor (HCF), highest common divisor (HCD), and greatest common measure (GCM).\nThe greatest common divisor is often written as\ngcd(a, b)\nor, more simply, as\n(a, b)\n, although the latter notation is ambiguous, also used for concepts such as an [ideal](https://bliptext.com/articles/ideal-ring-theory) in the [ring of integers](https://bliptext.com/articles/ring-of-integers), which is closely related to GCD.\nIf\ngcd(a, b) = 1\n, then a and b are said to be [coprime](https://bliptext.com/articles/coprime-integers) (or relatively prime).\nThis property does not imply that a or b are themselves [prime numbers](https://bliptext.com/articles/prime-number).\nFor example, 6 and 35 factor as 6 = 2 × 3 and 35 = 5 × 7, so they are not prime, but their prime factors are different, so 6 and 35 are coprime, with no common factors other than 1.\n[[File:24x60.svg|thumb|upright|alt=\"Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall.\"|A 24×60 rectangle is covered with ten 12×12 square tiles, where 12 is the GCD of 24 and 60. More generally, an\na×b\nrectangle can be covered with square tiles of side-length c only if c is a common divisor of a and b.]]\nLet\n. Since a and b are both multiples of g, they can be written\nand, and there is no larger number\nG > g\nfor which this is true.\nThe natural numbers m and n must be coprime, since any common factor could be factored out of m and n to make g greater.\nThus, any other number c that divides both a and b must also divide g. The greatest common divisor g of a and b is the unique (positive) common divisor of a and b that is divisible by any other common divisor c.\nThe greatest common divisor can be visualized as follows.\nConsider a rectangular area a by b, and any common divisor c that divides both a and b exactly.\nThe sides of the rectangle can be divided into segments of length c, which divides the rectangle into a grid of squares of side length c. The GCD g is the largest value of c for which this is possible.\nFor illustration, a\n24×60\nrectangular area can be divided into a grid of:\n1×1\nsquares,\n2×2\nsquares,\n3×3\nsquares,\n4×4\nsquares,\n6×6\nsquares or\n12×12\nsquares.\nTherefore,\n12\nis the GCD of\n24\nand\n60\n. A\n24×60\nrectangular area can be divided into a grid of\n12×12\nsquares, with two squares along one edge (\n) and five squares along the other (\n).\nThe greatest common divisor of two numbers a and b 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 a and b. For example, since\n1386\ncan be factored into\n2 × 3 × 3 × 7 × 11\n, and\n3213\ncan be factored into\n3 × 3 × 3 × 7 × 17\n, the GCD of\n1386\nand\n3213\nequals\n, the product of their shared prime factors (with 3 repeated since\n3 × 3\ndivides both). If two numbers have no common prime factors, their GCD is\n1\n(obtained here as an instance of the [empty product](https://bliptext.com/articles/empty-product)); in other words, they are coprime.\nA key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors.\n[Factorization](https://bliptext.com/articles/integer-factorization) of large integers is believed to be a computationally very difficult problem, and the security of many widely used [cryptographic protocols](https://bliptext.com/articles/cryptographic-protocol) is based upon its infeasibility.\nAnother definition of the GCD is helpful in advanced mathematics, particularly [ring theory](https://bliptext.com/articles/ring-theory).\nThe greatest common divisor g of two nonzero numbers a and b is also their smallest positive integral linear combination, that is, the smallest positive number of the form\nua + vb\nwhere u and v are integers.\nThe set of all integral linear combinations of a and b is actually the same as the set of all multiples of g (mg, where m is an integer).\nIn modern mathematical language, the [ideal](https://bliptext.com/articles/ideal-ring-theory) generated by a and b is the [ideal](https://bliptext.com/articles/ideal-ring-theory) generated by g alone (an [ideal](https://bliptext.com/articles/ideal-ring-theory) generated by a single element is called a principal [ideal](https://bliptext.com/articles/ideal-ring-theory), and all [ideal](https://bliptext.com/articles/ideal-ring-theory)s of the integers are principal [ideal](https://bliptext.com/articles/ideal-ring-theory)s).\nSome properties of the GCD are in fact easier to see with this description, for instance the fact that any common divisor of a and b also divides the GCD (it divides both terms of\nua + vb\n). The equivalence of this GCD definition with the other definitions is described below.\nThe GCD of three or more numbers equals the product of the prime factors common to all the numbers, but it can also be calculated by repeatedly taking the GCDs of pairs of numbers.\nFor example,\ngcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b).\nThus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers.\n\n# Description\n\n## Procedure\nThe 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: with.\nThe integer r_{n-1} will then be the GCD and we can state.\nThe algorithm indicates how to construct the intermediate remainders r_k via [division-with-remainder](https://bliptext.com/articles/euclidean-division) on the preceding pair by finding an integer quotient q_k so that:\nBecause the sequence of non-negative integers \\{ r_k \\} is strictly decreasing, it eventually [must terminate](https://bliptext.com/articles/well-ordering-principle).\nIn 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.\nIn fact, the algorithm will always terminate at the n-th step with r_n equal to zero.\nTo illustrate, suppose the GCD of 1071 and 462 is requested.\nThe sequence is initially and in order to find r_0, we need to find integers q_0 and such that:\nThis is the quotient q_0 = 2 since.\nThis determines r_0 = 147 and so the sequence is now.\nThe next step is to continue the sequence to find r_1 by finding integers q_1 and r_1 < r_0 such that:\nThis is the quotient q_1 = 3 since.\nThis determines r_1 = 21 and so the sequence is now.\nThe next step is to continue the sequence to find r_2 by finding integers q_2 and r_2 < r_1 such that:\nThis is the quotient q_2 = 7 since.\nThis determines r_2 = 0 and so the sequence is completed as as no further non-negative integer smaller than 0 can be found.\nThe penultimate remainder 21 is therefore the requested GCD:\nWe 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 as the sequence of remainders will be.\nIf a < b, then we can also continue since, suggesting the next remainder should be a itself, and the sequence is.\nNormally, this would be invalid because it breaks the requirement but now we have a < b by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal.\nTherefore, 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 < b and everything continues as above.\nThe only modifications that need to be made are that only for k \\ge 0, and that the sub-sequence of non-negative integers for k \\ge 0 is strictly decreasing, therefore excluding a = r_{-2} from both statements.\n\n## Proof of validity\nThe validity of the Euclidean algorithm can be proven by a two-step argument.\nIn the first step, the final nonzero remainder rN−1 is shown to divide both a and b.\nSince it is a common divisor, it must be less than or equal to the greatest common divisor g.\nIn the second step, it is shown that any common divisor of a and b, including g, must divide rN−1; therefore, g must be less than or equal to rN−1.\nThese two opposite inequalities imply rN−1 = g.\nTo demonstrate that rN−1 divides both a and b (the first step), rN−1 divides its predecessor rN−2\nrN−2 = qN rN−1\nsince the final remainder rN is zero.\nrN−1 also divides its next predecessor rN−3\nrN−3 = qN−1 rN−2 + rN−1\nbecause it divides both terms on the right-hand side of the equation.\nIterating the same argument, rN−1 divides all the preceding remainders, including a and b.\nNone of the preceding remainders rN−2, rN−3, etc. divide a and b, since they leave a remainder.\nSince rN−1 is a common divisor of a and b, rN−1 ≤ g.\nIn 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 rk. By definition, a and b can be written as multiples of c : a = mc and b = nc, where m and n are natural numbers.\nTherefore, c divides the initial remainder r0, since r0 = a − q0b = mc − q0nc = (m − q0n)c.\nAn analogous argument shows that c also divides the subsequent remainders r1, r2, etc. Therefore, the greatest common divisor g must divide rN−1, which implies that g ≤ rN−1.\nSince the first part of the argument showed the reverse (rN−1 ≤ g), it follows that g = rN−1.\nThus, g is the greatest common divisor of all the succeeding pairs:\ng = gcd(a, b) = gcd(b, r0) = gcd(r0, r1) = … = gcd(rN−2, rN−1) = rN−1.\n\n## Worked example\nFor illustration, the Euclidean algorithm can be used to find the greatest common divisor of a = 1071 and b = 462.\nTo begin, multiples of 462 are subtracted from 1071 until the remainder is less than 462.\nTwo such multiples can be subtracted (q0 = 2), leaving a remainder of 147:\n1071 = 2 × 462 + 147.\nThen multiples of 147 are subtracted from 462 until the remainder is less than 147.\nThree multiples can be subtracted (q1 = 3), leaving a remainder of 21:\n462 = 3 × 147 + 21.\nThen multiples of 21 are subtracted from 147 until the remainder is less than 21.\nSeven multiples can be subtracted (q2 = 7), leaving no remainder:\n147 = 7 × 21 + 0.\nSince the last remainder is zero, the algorithm ends with 21 as the greatest common divisor of 1071 and 462.\nThis agrees with the gcd(1071, 462) found by prime factorization [above](https://bliptext.com/articles/).\nIn tabular form, the steps are:\n\n## Visualization\nThe Euclidean algorithm can be visualized in terms of the tiling analogy given above for the greatest common divisor.\nAssume that we wish to cover an a×b rectangle with square tiles exactly, where a is the larger of the two numbers.\nWe first attempt to tile the rectangle using b×b square tiles; however, this leaves an r0×b residual rectangle untiled, where r0 < b.\nWe then attempt to tile the residual rectangle with r0×r0 square tiles.\nThis leaves a second residual rectangle r1×r0, which we attempt to tile using r1×r1 square tiles, and so on.\nThe sequence ends when there is no residual rectangle, i.e., when the square tiles cover the previous residual rectangle exactly.\nThe length of the sides of the smallest square tile is the GCD of the dimensions of the original rectangle.\nFor example, the smallest square tile in the adjacent figure is 21×21 (shown in red), and 21 is the GCD of 1071 and 462, the dimensions of the original rectangle (shown in green).\n\n## Euclidean division\nAt every step k, the Euclidean algorithm computes a quotient qk and remainder rk from two numbers rk−1 and rk−2\nrk−2 = qk rk−1 + rk\nwhere the rk is non-negative and is strictly less than the [absolute value](https://bliptext.com/articles/absolute-value) of rk−1.\nThe theorem which underlies the definition of the [Euclidean division](https://bliptext.com/articles/euclidean-division) ensures that such a quotient and remainder always exist and are unique.\nIn Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is, rk−1 is subtracted from rk−2 repeatedly until the remainder rk is smaller than rk−1.\nAfter that rk and rk−1 are exchanged and the process is iterated.\nEuclidean division reduces all the steps between two exchanges into a single step, which is thus more efficient.\nMoreover, the quotients are not needed, thus one may replace Euclidean division by the [modulo operation](https://bliptext.com/articles/modulo-operation), which gives only the remainder.\nThus the iteration of the Euclidean algorithm becomes simply\nrk = rk−2 mod rk−1.\n\n## Implementations\nImplementations of the algorithm may be expressed in [pseudocode](https://bliptext.com/articles/pseudocode).\nFor example, the division-based version may be [programmed](https://bliptext.com/articles/computer-programming) as\n**function** gcd(a, b) **while** b ≠ 0\nt := b b := a **mod** b a := t **return** a\nAt the beginning of the kth iteration, the variable b holds the latest remainder rk−1, whereas the variable a holds its predecessor, rk−2.\nThe step b := a mod b is equivalent to the above recursion formula rk ≡ rk−2 mod rk−1.\nThe [temporary variable](https://bliptext.com/articles/temporary-variable) t holds the value of rk−1 while the next remainder rk is being calculated.\nAt the end of the loop iteration, the variable b holds the remainder rk, whereas the variable a holds its predecessor, rk−1.\n(If negative inputs are allowed, or if the **mod** function may return negative values, the last line must be changed into **return abs**(a).)\nIn the subtraction-based version, which was Euclid's original version, the remainder calculation is replaced by repeated subtraction.\nContrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops when a = b:\n**function** gcd(a, b) **while** a ≠ b **if** a > b a := a − b **else**\nb := b − a **return** a\nThe variables a and b alternate holding the previous remainders rk−1 and rk−2.\nAssume that a is larger than b at the beginning of an iteration; then a equals rk−2, since rk−2 > rk−1.\nDuring the loop iteration, a is reduced by multiples of the previous remainder b until a is smaller than b.\nThen a is the next remainder rk. Then b is reduced by multiples of a until it is again smaller than a, giving the next remainder rk+1, and so on.\nThe recursive version is based on the equality of the GCDs of successive remainders and the stopping condition gcd(rN−1, 0) = rN−1.\n**function** gcd(a, b) **if** b = 0\n**return** a **else**\n**return** gcd(b, a **mod** b)\n(As above, if negative inputs are allowed, or if the **mod** function may **return** negative values, the instruction \"**return** a\" must be changed into \"**return** max(a, −a)\".)\nFor illustration, the gcd(1071, 462) is calculated from the equivalent gcd(462, 1071 mod 462) = gcd(462, 147).\nThe latter GCD is calculated from the gcd(147, 462 mod 147) = gcd(147, 21), which in turn is calculated from the gcd(21, 147 mod 21) = gcd(21, 0) = 21.\n\n## Method of least absolute remainders\nIn 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.\nPreviously, the equation\nrk−2 = qk rk−1 + rk\nassumed that\nrk−1\n. However, an alternative negative remainder\nek\ncan be computed:\nrk−2 = (qk + 1) rk−1 + ek\nif\nrk−1 > 0\nor\nrk−2 = (qk − 1) rk−1 + ek\nif\nrk−1 < 0\n.\nIf\nrk\nis replaced by\nek.\nwhen\nek\n, then one gets a variant of Euclidean algorithm such that\nrk\nat each step.\n[Leopold Kronecker](https://bliptext.com/articles/leopold-kronecker) has shown that this version requires the fewest steps of any version of Euclid's algorithm.\nMore generally, it has been proven that, for every input numbers a and b, the number of steps is minimal if and only if\nqk\nis chosen in order that where \\varphi is the [golden ratio](https://bliptext.com/articles/golden-ratio).\n\n# Historical development\nThe Euclidean algorithm is one of the oldest algorithms in common use.\nIt appears in Euclid's Elements (c. 300 BC), specifically in Book 7 (Propositions 1–2) and Book 10 (Propositions 2–3).\nIn Book 7, the algorithm is formulated for integers, whereas in Book 10, it is formulated for lengths of line segments.\n(In modern usage, one would say it was formulated there for [real numbers](https://bliptext.com/articles/real-number). But lengths, areas, and volumes, represented as [real numbers](https://bliptext.com/articles/real-number) 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](https://bliptext.com/articles/real-number) was unknown at that time.) The latter algorithm is geometrical.\nThe GCD of two lengths a and b corresponds to the greatest length g that measures a and b evenly; in other words, the lengths a and b are both integer multiples of the length g.\nThe algorithm was probably not discovered by [Euclid](https://bliptext.com/articles/euclid), who compiled results from earlier mathematicians in his Elements.\nThe mathematician and historian [B. L. van der Waerden](https://bliptext.com/articles/bartel-leendert-van-der-waerden) suggests that Book VII derives from a textbook on [number theory](https://bliptext.com/articles/number-theory) written by mathematicians in the school of [Pythagoras](https://bliptext.com/articles/pythagoras).\nThe algorithm was probably known by [Eudoxus of Cnidus](https://bliptext.com/articles/eudoxus-of-cnidus) (about 375 BC).\nThe algorithm may even pre-date Eudoxus, judging from the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid and [Aristotle](https://bliptext.com/articles/aristotle).\nClaude Brezinski, following remarks by [Pappus of Alexandria](https://bliptext.com/articles/pappus-of-alexandria), credits the algorithm to [Theaetetus](https://bliptext.com/articles/theaetetus-mathematician) (c. 417 – c. 369 BC).\nCenturies later, Euclid's algorithm was discovered independently both in India and in China, primarily to solve [Diophantine equations](https://bliptext.com/articles/diophantine-equation) that arose in astronomy and making accurate calendars.\nIn the late 5th century, the Indian mathematician and astronomer [Aryabhata](https://bliptext.com/articles/aryabhata) described the algorithm as the \"pulverizer\", perhaps because of its effectiveness in solving Diophantine equations.\nAlthough a special case of the [Chinese remainder theorem](https://bliptext.com/articles/chinese-remainder-theorem) had already been described in the Chinese book [Sunzi Suanjing](https://bliptext.com/articles/sunzi-suanjing), the general solution was published by [Qin Jiushao](https://bliptext.com/articles/qin-jiushao) in his 1247 book Shushu Jiuzhang (數書九章 [Mathematical Treatise in Nine Sections](https://bliptext.com/articles/mathematical-treatise-in-nine-sections)).\nThe Euclidean algorithm was first described numerically and popularized in Europe in the second edition of [Bachet's](https://bliptext.com/articles/claude-gaspard-bachet-de-m-ziriac) Problèmes plaisants et délectables (Pleasant and enjoyable problems, 1624).\nIn Europe, it was likewise used to solve Diophantine equations and in developing [continued fractions](https://bliptext.com/articles/simple-continued-fraction).\nThe [extended Euclidean algorithm](https://bliptext.com/articles/extended-euclidean-algorithm) was published by the English mathematician [Nicholas Saunderson](https://bliptext.com/articles/nicholas-saunderson), who attributed it to [Roger Cotes](https://bliptext.com/articles/roger-cotes) as a method for computing continued fractions efficiently.\nIn the 19th century, the Euclidean algorithm led to the development of new number systems, such as [Gaussian integers](https://bliptext.com/articles/gaussian-integer) and [Eisenstein integers](https://bliptext.com/articles/eisenstein-integer).\nIn 1815, [Carl Gauss](https://bliptext.com/articles/carl-friedrich-gauss) used the Euclidean algorithm to demonstrate unique factorization of [Gaussian integers](https://bliptext.com/articles/gaussian-integer), although his work was first published in 1832.\nGauss mentioned the algorithm in his [Disquisitiones Arithmeticae](https://bliptext.com/articles/disquisitiones-arithmeticae) (published 1801), but only as a method for [continued fractions](https://bliptext.com/articles/continued-fraction).\n[Peter Gustav Lejeune Dirichlet](https://bliptext.com/articles/peter-gustav-lejeune-dirichlet) seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory.\nLejeune 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.\nLejeune Dirichlet's lectures on number theory were edited and extended by [Richard Dedekind](https://bliptext.com/articles/richard-dedekind), who used Euclid's algorithm to study [algebraic integers](https://bliptext.com/articles/algebraic-integer), a new general type of number.\nFor example, Dedekind was the first to prove [Fermat's two-square theorem](https://bliptext.com/articles/fermat-s-theorem-on-sums-of-two-squares) using the unique factorization of Gaussian integers.\nDedekind also defined the concept of a [Euclidean domain](https://bliptext.com/articles/euclidean-domain), a number system in which a generalized version of the Euclidean algorithm can be defined (as described [below](https://bliptext.com/articles/)).\nIn the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of [ideals](https://bliptext.com/articles/ideal-ring-theory).\nOther applications of Euclid's algorithm were developed in the 19th century.\nIn 1829, [Charles Sturm](https://bliptext.com/articles/jacques-charles-fran-ois-sturm) showed that the algorithm was useful in the [Sturm chain](https://bliptext.com/articles/sturm-s-theorem) method for counting the real roots of polynomials in any given interval.\nThe Euclidean algorithm was the first [integer relation algorithm](https://bliptext.com/articles/integer-relation-algorithm), which is a method for finding integer relations between commensurate real numbers.\nSeveral novel [integer relation algorithms](https://bliptext.com/articles/integer-relation-algorithm) have been developed, such as the algorithm of [Helaman Ferguson](https://bliptext.com/articles/helaman-ferguson) and R.W. Forcade (1979) and the [LLL algorithm](https://bliptext.com/articles/lenstra-lenstra-lov-sz-lattice-basis-reduction-algorithm).\nIn 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called The Game of Euclid, which has an optimal strategy.\nThe players begin with two piles of a and b stones.\nThe players take turns removing m multiples of the smaller pile from the larger.\nThus, if the two piles consist of x and y stones, where x is larger than y, the next player can reduce the larger pile from x stones to x − my stones, as long as the latter is a nonnegative integer.\nThe winner is the first player to reduce one pile to zero stones.\n# [The Euclidean algorithm was probably invented before Euclid, depicted here holding a compass in a painting of about 1474. | upload.wikimedia.org/wikipedia/commons/9/9e/Euklid.jpg]\n\n# Mathematical applications\n\n## Bézout's identity\nBézout's identity states that the greatest common divisor g of two integers a and b can be represented as a linear sum of the original two numbers a and b.\nIn other words, it is always possible to find integers s and t such that g = sa + tb.\nThe integers s and t can be calculated from the quotients q0, q1, etc. by reversing the order of equations in Euclid's algorithm.\nBeginning with the next-to-last equation, g can be expressed in terms of the quotient qN−1 and the two preceding remainders, rN−2 and rN−3:\ng = rN−1 = rN−3 − qN−1 rN−2.\nThose two remainders can be likewise expressed in terms of their quotients and preceding remainders,\nrN−2 = rN−4 − qN−2 rN−3\nand\nrN−3 = rN−5 − qN−3 rN−4.\nSubstituting these formulae for rN−2 and rN−3 into the first equation yields g as a linear sum of the remainders rN−4 and rN−5.\nThe process of substituting remainders by formulae involving their predecessors can be continued until the original numbers a and b are reached:\nr2 = r0 − q2 r1\nr1 = b − q1 r0\nr0 = a − q0 b.\nAfter all the remainders r0, r1, etc. have been substituted, the final equation expresses g as a linear sum of a and b, so that g = sa + tb.\nThe Euclidean algorithm, and thus Bézout's identity, can be generalized to the context of [Euclidean domains](https://bliptext.com/articles/euclidean-domain).\n\n## Principal ideals and related problems\nBézout's identity provides yet another definition of the greatest common divisor g of two numbers a and b.\nConsider the set of all numbers ua + vb, where u and v are any two integers.\nSince a and b are both divisible by g, every number in the set is divisible by g.\nIn other words, every number of the set is an integer multiple of g.\nThis is true for every common divisor of a and b.\nHowever, unlike other common divisors, the greatest common divisor is a member of the set; by Bézout's identity, choosing u = s and v = t gives g.\nA smaller common divisor cannot be a member of the set, since every member of the set must be divisible by g.\nConversely, any multiple m of g can be obtained by choosing u = ms and v = mt, where s and t are the integers of Bézout's identity.\nThis may be seen by multiplying Bézout's identity by m,\nmg = msa + mtb.\nTherefore, the set of all numbers ua + vb is equivalent to the set of multiples m of g.\nIn other words, the set of all possible sums of integer multiples of two numbers (a and b) is equivalent to the set of multiples of gcd(a, b).\nThe GCD is said to be the generator of the [ideal](https://bliptext.com/articles/ideal-ring-theory) of a and b.\nThis GCD definition led to the modern [abstract algebraic](https://bliptext.com/articles/abstract-algebra) concepts of a [principal ideal](https://bliptext.com/articles/principal-ideal) (an ideal generated by a single element) and a [principal ideal](https://bliptext.com/articles/principal-ideal) [domain](https://bliptext.com/articles/domain-ring-theory) (a [domain](https://bliptext.com/articles/domain-ring-theory) in which every ideal is a [principal ideal](https://bliptext.com/articles/principal-ideal)).\nCertain problems can be solved using this result.\nFor example, consider two measuring cups of volume a and b.\nBy adding/subtracting u multiples of the first cup and v multiples of the second cup, any volume ua + vb can be measured out.\nThese volumes are all multiples of g = gcd(a, b).\n\n## Extended Euclidean algorithm\nThe integers s and t of Bézout's identity can be computed efficiently using the [extended Euclidean algorithm](https://bliptext.com/articles/extended-euclidean-algorithm).\nThis extension adds two recursive equations to Euclid's algorithm\nsk = sk−2 − qksk−1\ntk = tk−2 − qktk−1\nwith the starting values\ns−2 = 1, t−2 = 0\ns−1 = 0, t−1 = 1.\nUsing this recursion, Bézout's integers s and t are given by s = sN and t = tN, where N+1 is the step on which the algorithm terminates with rN+1 = 0.\nThe validity of this approach can be shown by induction.\nAssume that the recursion formula is correct up to step k − 1 of the algorithm; in other words, assume that\nrj = sj a + tj b\nfor all j less than k.\nThe kth step of the algorithm gives the equation\nrk = rk−2 − qkrk−1.\nSince the recursion formula has been assumed to be correct for rk−2 and rk−1, they may be expressed in terms of the corresponding s and t variables\nrk = (sk−2 a + tk−2 b) − qk(sk−1 a + tk−1 b).\nRearranging this equation yields the recursion formula for step k, as required\nrk = sk a + tk b = (sk−2 − qksk−1) a + (tk−2 − qktk−1) b.\n\n## Matrix method\nThe integers s and t can also be found using an equivalent [matrix](https://bliptext.com/articles/matrix-mathematics) method.\nThe sequence of equations of Euclid's algorithm\ncan be written as a product of 2×2 quotient matrices multiplying a two-dimensional remainder vector\nLet **M** represent the product of all the quotient matrices\nThis simplifies the Euclidean algorithm to the form\nTo express g as a linear sum of a and b, both sides of this equation can be multiplied by the [inverse](https://bliptext.com/articles/invertible-matrix) of the matrix **M**.\nThe [determinant](https://bliptext.com/articles/determinant) of **M** equals (−1)N+1, since it equals the product of the [determinant](https://bliptext.com/articles/determinant)s of the quotient matrices, each of which is negative one.\nSince the determinant of ****M**** is never zero, the vector of the final remainders can be solved using the inverse of ****M****\nSince the top equation gives\ng = (−1)N+1 ( m22 a − m12 b),\nthe two integers of Bézout's identity are s = (−1)N+1m22 and t = (−1)Nm12.\nThe matrix method is as efficient as the equivalent recursion, with two multiplications and two additions per step of the Euclidean algorithm.\n\n## Euclid's lemma and unique factorization\nBézout's identity is essential to many applications of Euclid's algorithm, such as demonstrating the [unique factorization](https://bliptext.com/articles/fundamental-theorem-of-arithmetic) of numbers into prime factors.\nTo illustrate this, suppose that a number L can be written as a product of two factors u and v, that is, L = uv.\nIf another number w also divides L but is coprime with u, then w must divide v, by the following argument: If the greatest common divisor of u and w is 1, then integers s and t can be found such that\n1 = su + tw\nby Bézout's identity.\nMultiplying both sides by v gives the relation:\nv = suv + twv = sL + twv\nSince w divides both terms on the right-hand side, it must also divide the left-hand side, v.\nThis result is known as [Euclid's lemma](https://bliptext.com/articles/euclid-s-lemma).\nSpecifically, if a prime number divides L, then it must divide at least one factor of L.\nConversely, if a number w is coprime to each of a series of numbers a1, a2, ..., an, then w is also coprime to their product, a1 × a2 × ... × an.\nEuclid's lemma suffices to prove that every number has a unique factorization into prime numbers.\nTo see this, assume the contrary, that there are two independent factorizations of L into m and n prime factors, respectively\nL = p1p2…pm = q1q2…qn.\nSince 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.\nIteratively dividing by the p factors shows that each p has an equal counterpart q; the two prime factorizations are identical except for their order.\nThe unique factorization of numbers into primes has many applications in mathematical proofs, as shown below.\n\n## Linear Diophantine equations\n[Diophantine equations](https://bliptext.com/articles/diophantine-equation) are equations in which the solutions are restricted to integers; they are named after the 3rd-century Alexandrian mathematician [Diophantus](https://bliptext.com/articles/diophantus).\nA typical linear Diophantine equation seeks integers x and y such that\nax + by = c\nwhere a, b and c are given integers.\nThis can be written as an equation for x in [modular arithmetic](https://bliptext.com/articles/modular-arithmetic):\nax ≡ c mod b.\nLet g be the greatest common divisor of a and b.\nBoth terms in ax + by are divisible by g; therefore, c must also be divisible by g, or the equation has no solutions.\nBy dividing both sides by c/g, the equation can be reduced to Bezout's identity\nsa + tb = g\nwhere s and t can be found by the [extended Euclidean algorithm](https://bliptext.com/articles/extended-euclidean-algorithm).\nThis provides one solution to the Diophantine equation, x1 = s (c/g) and y1 = t (c/g).\nIn general, a linear Diophantine equation has no solutions, or an infinite number of solutions.\nTo find the latter, consider two solutions, (x1, y1) and (x2, y2), where\nax1 + by1 = c = ax2 + by2\nor equivalently\na(x1 − x2) = b(y2 − y1).\nTherefore, the smallest difference between two x solutions is b/g, whereas the smallest difference between two y solutions is a/g.\nThus, the solutions may be expressed as\nx = x1 − bu/g\ny = y1 + au/g\n.\nBy allowing u to vary over all possible integers, an infinite family of solutions can be generated from a single solution (x1, y1).\nIf the solutions are required to be positive integers (x > 0, y > 0), only a finite number of solutions may be possible.\nThis 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](https://bliptext.com/articles/system-of-linear-equations) when the solutions can be any [real number](https://bliptext.com/articles/real-number) (see [Underdetermined system](https://bliptext.com/articles/underdetermined-system)).\n# [Plot of a linear Diophantine equation, 9x + 12y = 483. The solutions are shown as blue circles. | upload.wikimedia.org/wikipedia/commons/9/94/Diophante///Bezout.svg]\n\n## Multiplicative inverses and the RSA algorithm\nA [finite field](https://bliptext.com/articles/finite-field) is a set of numbers with four generalized operations.\nThe operations are called addition, subtraction, multiplication and division and have their usual properties, such as [commutativity](https://bliptext.com/articles/commutativity), [associativity](https://bliptext.com/articles/associativity) and [distributivity](https://bliptext.com/articles/distributivity).\nAn example of a finite field is the set of 13 numbers {0, 1, 2, ..., 12} using [modular arithmetic](https://bliptext.com/articles/modular-arithmetic).\nIn this field, the results of any mathematical operation (addition, subtraction, multiplication, or division) is reduced [modulo](https://bliptext.com/articles/modulo-operation) 13; that is, multiples of 13 are added or subtracted until the result is brought within the range 0–12.\nFor example, the result of 5 × 7 = 35 mod 13 = 9.\nSuch finite fields can be defined for any prime p; using more sophisticated definitions, they can also be defined for any power m of a prime pm. Finite fields are often called [Galois](https://bliptext.com/articles/variste-galois) fields, and are abbreviated as GF(p) or GF(pm).\nIn such a field with m numbers, every nonzero element a has a unique [modular multiplicative inverse](https://bliptext.com/articles/modular-multiplicative-inverse), a−1 such that aa−1 = a−1a ≡ 1 mod m. This inverse can be found by solving the congruence equation ax ≡ 1 mod m, or the equivalent linear Diophantine equation\nax + my = 1.\nThis equation can be solved by the Euclidean algorithm, as described [above](https://bliptext.com/articles/).\nFinding multiplicative inverses is an essential step in the [RSA algorithm](https://bliptext.com/articles/rsa-algorithm), which is widely used in [electronic commerce](https://bliptext.com/articles/electronic-commerce); specifically, the equation determines the integer used to decrypt the message.\nAlthough the RSA algorithm uses [rings](https://bliptext.com/articles/ring-mathematics) rather than fields, the Euclidean algorithm can still be used to find a multiplicative inverse where one exists.\nThe Euclidean algorithm also has other applications in [error-correcting codes](https://bliptext.com/articles/error-correcting-code); for example, it can be used as an alternative to the [Berlekamp–Massey algorithm](https://bliptext.com/articles/berlekamp-massey-algorithm) for decoding [BCH](https://bliptext.com/articles/bch-code) and [Reed–Solomon codes](https://bliptext.com/articles/reed-solomon-code), which are based on Galois fields.\n\n## Chinese remainder theorem\nEuclid's algorithm can also be used to solve multiple linear Diophantine equations.\nSuch equations arise in the [Chinese remainder theorem](https://bliptext.com/articles/chinese-remainder-theorem), which describes a novel method to represent an integer x.\nInstead of representing an integer by its digits, it may be represented by its remainders xi modulo a set of N coprime numbers mi:\nThe 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\nThus, each Mi is the product of all the moduli except mi. The solution depends on finding N new numbers hi such that\nWith these numbers hi, any integer x can be reconstructed from its remainders xi by the equation\nSince these numbers hi are the multiplicative inverses of the Mi, they may be found using Euclid's algorithm as described in the previous subsection.\n\n## Stern–Brocot tree\nThe Euclidean algorithm can be used to arrange the set of all positive [rational numbers](https://bliptext.com/articles/rational-number) into an infinite [binary search tree](https://bliptext.com/articles/binary-search-tree), called the [Stern–Brocot tree](https://bliptext.com/articles/stern-brocot-tree).\nThe 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.\nA 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.\nThe 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.\nThis fact can be used to prove that each positive rational number appears exactly once in this tree.\nFor example, 3/4 can be found by starting at the root, going to the left once, then to the right twice:\nThe Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called the [Calkin–Wilf tree](https://bliptext.com/articles/calkin-wilf-tree).\nThe 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.\n# [The Stern–Brocot tree, and the Stern–Brocot sequences of order i for i = 1, 2, 3, 4 | upload.wikimedia.org/wikipedia/commons/3/37/SternBrocotTree.svg]\n\n## Continued fractions\nThe Euclidean algorithm has a close relationship with [continued fractions](https://bliptext.com/articles/continued-fraction).\nThe sequence of equations can be written in the form\nThe last term on the right-hand side always equals the inverse of the left-hand side of the next equation.\nThus, the first two equations may be combined to form\nThe third equation may be used to substitute the denominator term r1/r0, yielding\nThe final ratio of remainders rk/rk−1 can always be replaced using the next equation in the series, up to the final equation.\nThe result is a continued fraction\nIn the worked example [above](https://bliptext.com/articles/), the gcd(1071, 462) was calculated, and the quotients qk were 2, 3 and 7, respectively.\nTherefore, the fraction 1071/462 may be written\nas can be confirmed by calculation.\n\n## Factorization algorithms\nCalculating a greatest common divisor is an essential step in several [integer factorization](https://bliptext.com/articles/integer-factorization) algorithms, such as [Pollard's rho algorithm](https://bliptext.com/articles/pollard-s-rho-algorithm), [Shor's algorithm](https://bliptext.com/articles/shor-s-algorithm), [Dixon's factorization method](https://bliptext.com/articles/dixon-s-factorization-method) and the [Lenstra elliptic curve factorization](https://bliptext.com/articles/lenstra-elliptic-curve-factorization).\nThe Euclidean algorithm may be used to find this GCD efficiently.\n[Continued fraction factorization](https://bliptext.com/articles/continued-fraction-factorization) uses continued fractions, which are determined using Euclid's algorithm.\n\n# Algorithmic efficiency\nThe computational efficiency of Euclid's algorithm has been studied thoroughly.\nThis efficiency can be described by the number of division steps the algorithm requires, multiplied by the computational expense of each step.\nThe first known analysis of Euclid's algorithm is due to [A. A. L. Reynaud](https://bliptext.com/articles/antoine-andr-louis-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.\nLater, in 1841, [P. J. E. Finck](https://bliptext.com/articles/pierre-joseph-tienne-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.\n[Émile Léger](https://bliptext.com/articles/mile-l-ger), in 1837, studied the worst case, which is when the inputs are consecutive [Fibonacci numbers](https://bliptext.com/articles/fibonacci-numbers).\nFinck's analysis was refined by [Gabriel Lamé](https://bliptext.com/articles/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.\nIn the [uniform cost model](https://bliptext.com/articles/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](https://bliptext.com/articles/constant-time), and Lamé's analysis implies that the total running time is also O(h).\nHowever, 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).\nIn this case the total time for all of the steps of the algorithm can be analyzed using a [telescoping series](https://bliptext.com/articles/telescoping-series), showing that it is also O(h2).\nModern algorithmic techniques based on the [Schönhage–Strassen algorithm](https://bliptext.com/articles/sch-nhage-strassen-algorithm) for fast integer multiplication can be used to speed this up, leading to [quasilinear algorithms](https://bliptext.com/articles/quasilinear-time) for the GCD.\n# [Number of steps in the Euclidean algorithm for gcd(x,y). Lighter (red and yellow) points indicate relatively few steps, whereas darker (violet and blue) points indicate more steps. The largest dark area follows the line y = Φx, where Φ is the golden ratio. | upload.wikimedia.org/wikipedia/commons/8/85/Euclidean///Algorithm///Running///Time.svg]\n\n## Number of steps\nThe number of steps to calculate the GCD of two natural numbers, a and b, may be denoted by T(a, b).\nIf g is the GCD of a and b, then a = mg and b = ng for two coprime numbers m and n.\nThen\nT(a, b) = T(m, n)\nas may be seen by dividing all the steps in the Euclidean algorithm by g.\nBy 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).\nTherefore, 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.\nThe recursive nature of the Euclidean algorithm gives another equation\nT(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1\nwhere T(x, 0) = 0 by assumption.\n\n### Worst-case\nIf 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](https://bliptext.com/articles/fibonacci-number) FN+2 and FN+1, respectively.\nMore precisely, if the Euclidean algorithm requires N steps for the pair a > b, then one has a ≥ FN+2 and b ≥ FN+1.\nThis can be shown by [induction](https://bliptext.com/articles/mathematical-induction).\nIf 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.\nNow assume that the result holds for all values of N up to M − 1.\nThe first step of the M-step algorithm is a = q0b + r0, and the Euclidean algorithm requires M − 1 steps for the pair b > r0.\nBy induction hypothesis, one has b ≥ FM+1 and r0 ≥ FM. Therefore, a = q0b + r0 ≥ b + r0 ≥ FM+1 + FM = FM+2,\nwhich is the desired inequality.\nThis proof, published by [Gabriel Lamé](https://bliptext.com/articles/gabriel-lam) in 1844, represents the beginning of [computational complexity theory](https://bliptext.com/articles/computational-complexity-theory), and also the first practical application of the Fibonacci numbers.\nThis 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).\nFor 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](https://bliptext.com/articles/golden-ratio).\nSince b ≥ φN−1, then N − 1 ≤ logφb.\nSince log10φ > 1/5, (N − 1)/5 < log10φ logφb = log10b.\nThus, N ≤ 5 log10b.\nThus, the Euclidean algorithm always needs less than O(h) divisions, where h is the number of digits in the smaller number b.\n\n### Average\nThe average number of steps taken by the Euclidean algorithm has been defined in three different ways.\nThe 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\nHowever, since T(a, b) fluctuates dramatically with the GCD of the two numbers, the averaged function T(a) is likewise \"noisy\".\nTo reduce this noise, a second average τ(a) is taken over all numbers coprime with a\nThere are φ(a) coprime integers less than a, where φ is [Euler's totient function](https://bliptext.com/articles/euler-s-totient-function).\nThis tau average grows smoothly with a\nwith the residual error being of order a−(1/6) + ε, where ε is [infinitesimal](https://bliptext.com/articles/infinitesimal).\nThe constant C in this formula is called [Porter's constant](https://bliptext.com/articles/porter-s-constant) and equals\nwhere γ is the [Euler–Mascheroni constant](https://bliptext.com/articles/euler-mascheroni-constant) and ζ' is the [derivative](https://bliptext.com/articles/derivative) of the [Riemann zeta function](https://bliptext.com/articles/riemann-zeta-function).\nThe leading coefficient (12/π2) ln 2 was determined by two independent methods.\nSince the first average can be calculated from the tau average by summing over the divisors d of a\nit can be approximated by the formula\nwhere Λ(d) is the [Mangoldt function](https://bliptext.com/articles/von-mangoldt-function).\nA 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\nSubstituting the approximate formula for T(a) into this equation yields an estimate for Y(n)\n\n## Computational expense per step\nIn 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\nrk−2 = qk rk−1 + rk.\nThe 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\nrk = rk−2 − qk rk−1.\nThe computational expense of dividing h-bit numbers scales as\nO(h(ℓ+1))\n, where ℓ is the length of the quotient.\nFor comparison, Euclid's original subtraction-based algorithm can be much slower.\nA single integer division is equivalent to the quotient q number of subtractions.\nIf the ratio of a and b is very large, the quotient is large and many subtractions will be required.\nOn the other hand, it has been shown that the quotients are very likely to be small integers.\nThe probability of a given quotient q is approximately\nln\nwhere\nu = (q + 1)2\n. 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.\nSince 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.\nThis is exploited in the [binary version](https://bliptext.com/articles/binary-gcd-algorithm) of Euclid's algorithm.\nCombining 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.\nLet\nh0, h1, ..., hN−1\nrepresent the number of digits in the successive remainders\nr0, r1, ..., rN−1\n. Since the number of steps N grows linearly with h, the running time is bounded by\n\n## Alternative methods\nEuclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity.\nFor comparison, the efficiency of alternatives to Euclid's algorithm may be determined.\nOne 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.\nThe common divisors can be found by dividing both numbers by successive integers from 2 to the smaller number b.\nThe number of steps of this approach grows linearly with b, or exponentially in the number of digits.\nAnother inefficient approach is to find the prime factors of one or both numbers.\nAs noted [above](https://bliptext.com/articles/), the GCD equals the product of the prime factors shared by the two numbers a and b.\nPresent methods for [prime factorization](https://bliptext.com/articles/integer-factorization) are also inefficient; many modern cryptography systems even rely on that inefficiency.\nThe [binary GCD algorithm](https://bliptext.com/articles/[binary](https://bliptext.com/articles/binary-numeral-system)-gcd-algorithm) is an efficient alternative that substitutes division with faster operations by exploiting the [binary](https://bliptext.com/articles/binary-numeral-system) representation used by computers.\nHowever, this alternative also scales like O(h²).\nIt is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way.\nAdditional efficiency can be gleaned by examining only the leading digits of the two numbers a and b.\nThe binary algorithm can be extended to other bases (k-ary algorithms), with up to fivefold increases in speed.\n[Lehmer's GCD algorithm](https://bliptext.com/articles/lehmer-s-gcd-algorithm) uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases.\nA recursive approach for very large integers (with more than 25,000 digits) leads to [quasilinear](https://bliptext.com/articles/quasilinear-time) integer GCD algorithms, such as those of Schönhage, and Stehlé and Zimmermann.\nThese algorithms exploit the 2×2 matrix form of the Euclidean algorithm given [above](https://bliptext.com/articles/).\nThese quasilinear methods generally scale as\nO(h log h2 log log h).\n\n# Generalizations\nAlthough 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](https://bliptext.com/articles/polynomial), [quadratic integers](https://bliptext.com/articles/quadratic-integer) and [Hurwitz quaternions](https://bliptext.com/articles/hurwitz-quaternion).\nIn the latter cases, the Euclidean algorithm is used to demonstrate the crucial property of unique factorization, i.e., that such numbers can be factored uniquely into [irreducible elements](https://bliptext.com/articles/irreducible-element), the counterparts of prime numbers.\nUnique factorization is essential to many proofs of number theory.\n\n## Rational and real numbers\nEuclid's algorithm can be applied to [real numbers](https://bliptext.com/articles/real-number), as described by Euclid in Book 10 of his [Elements](https://bliptext.com/articles/euclid-s-elements).\nThe 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:\na = mg\nand\nb = ng\n, where m and n are [integers](https://bliptext.com/articles/integer).\nThis identification is equivalent to finding an [integer relation](https://bliptext.com/articles/integer-relation-algorithm) among the real numbers a and b; that is, it determines integers s and t such that\nsa + tb = 0\n. If such an equation is possible, a and b are called commensurable lengths, otherwise they are [incommensurable lengths](https://bliptext.com/articles/commensurability-mathematics).\nThe real-number Euclidean algorithm differs from its integer counterpart in two respects.\nFirst, the remainders\nrk\nare real numbers, although the quotients\nqk\nare integers as before.\nSecond, the algorithm is not guaranteed to end in a finite number N of steps.\nIf it does, the fraction\na/b\nis a rational number, i.e., the ratio of two integers\nand can be written as a finite continued fraction\n[q0; q1, q2, ..., qN]\n. If the algorithm does not stop, the fraction\na/b\nis an [irrational number](https://bliptext.com/articles/irrational-number) and can be described by an infinite continued fraction\n[q0; q1, q2, …]\n. Examples of infinite continued fractions are the [golden ratio](https://bliptext.com/articles/golden-ratio)\nφ = [1; 1, 1, ...]\nand the [square root of two](https://bliptext.com/articles/square-root-of-2),\n√2 = [1; 2, 2, ...]\n. The algorithm is unlikely to stop, since [almost all](https://bliptext.com/articles/almost-all) ratios\na/b\nof two real numbers are irrational.\nAn infinite continued fraction may be truncated at a step\nk [q0; q1, q2, ..., qk]\nto yield an approximation to\na/b\nthat improves as k is increased.\nThe approximation is described by [convergents](https://bliptext.com/articles/convergent-continued-fraction)\nmk/nk\nwhere\nm−1 = n−2 = 1\nand\nm−2 = n−1 = 0\nare the initial values of the recursion.\nThe convergent\nmk/nk\nis the best [rational number](https://bliptext.com/articles/rational-number) approximation to\na/b\nwith denominator\nnk\n\n## Polynomials\nPolynomials in a single variable x can be added, multiplied and factored into [irreducible polynomials](https://bliptext.com/articles/irreducible-polynomial), which are the analogs of the prime numbers for integers.\nThe greatest common divisor polynomial\ng(x)\nof two polynomials\na(x)\nand\nb(x)\nis defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm.\nThe basic procedure is similar to that for integers.\nAt each step k, a quotient polynomial\nqk(x)\nand a remainder polynomial\nrk(x)\nare identified to satisfy the recursive equation\nwhere\nr−2(x) = a(x)\nand\nr−1(x) = b(x)\n. 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:\ndeg[rk(x)] < deg[rk−1(x)]\n. Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps.\nThe last nonzero remainder is the greatest common divisor of the original two polynomials,\na(x)\nand\nb(x)\n.\nFor example, consider the following two quartic polynomials, which each factor into two quadratic polynomials\n[Dividing](https://bliptext.com/articles/polynomial-long-division)\na(x)\nby\nb(x)\nyields a remainder\nr0(x) = x3 + (2/3)x2 + (5/3)x − (2/3)\n. In the next step,\nb(x)\nis divided by\nr0(x)\nyielding a remainder\nr1(x) = x2 + x + 2\n. Finally, dividing\nr0(x)\nby\nr1(x)\nyields a zero remainder, indicating that\nr1(x)\nis the greatest common divisor polynomial of\na(x)\nand\nb(x)\n, consistent with their factorization.\nMany of the applications described above for integers carry over to polynomials.\nThe Euclidean algorithm can be used to solve linear Diophantine equations and Chinese remainder problems for polynomials; continued fractions of polynomials can also be defined.\nThe polynomial Euclidean algorithm has other applications, such as [Sturm chains](https://bliptext.com/articles/sturm-chain), a method for counting the [zeros of a polynomial](https://bliptext.com/articles/zero-of-a-function) that lie inside a given [real interval](https://bliptext.com/articles/interval-mathematics).\nThis in turn has applications in several areas, such as the [Routh–Hurwitz stability criterion](https://bliptext.com/articles/routh-hurwitz-stability-criterion) in [control theory](https://bliptext.com/articles/control-theory).\nFinally, the coefficients of the polynomials need not be drawn from integers, real numbers or even the complex numbers.\nFor example, the coefficients may be drawn from a general field, such as the finite fields\nGF(p)\ndescribed above.\nThe corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.\n\n## Gaussian integers\n[[File:Gaussian primes.png|thumb|alt=\"A set of dots lying within a circle. The pattern of dots has fourfold symmetry, i.e., rotations by 90 degrees leave the pattern unchanged. The pattern can also be mirrored about four lines passing through the center of the circle: the vertical and horizontal axes, and the two diagonal lines at ±45 degrees.\"|Distribution of Gaussian primes\nu + vi\nin the complex plane, with norms\nu2 + v2\nless than 500]]\nThe [Gaussian integers](https://bliptext.com/articles/gaussian-integer) are [complex numbers](https://bliptext.com/articles/complex-number) of the form\nα = u + vi\n, where u and v are ordinary [integers](https://bliptext.com/articles/integer) and i is the [square root of negative one](https://bliptext.com/articles/imaginary-unit).\nBy defining an analog of the Euclidean algorithm, Gaussian integers can be shown to be uniquely factorizable, by the argument [above](https://bliptext.com/articles/).\nThis unique factorization is helpful in many applications, such as deriving all [Pythagorean triples](https://bliptext.com/articles/pythagorean-triple) or proving [Fermat's theorem on sums of two squares](https://bliptext.com/articles/fermat-s-theorem-on-sums-of-two-squares).\nIn general, the Euclidean algorithm is convenient in such applications, but not essential; for example, the theorems can often be proven by other arguments.\nThe Euclidean algorithm developed for two Gaussian integers α and β is nearly the same as that for ordinary integers, but differs in two respects.\nAs before, we set\nr−2 = α\nand\nr−1 = β\n, and the task at each step k is to identify a quotient\nqk\nand a remainder\nrk\nsuch that\nwhere every remainder is strictly smaller than its predecessor:\n<\n. The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are [complex numbers](https://bliptext.com/articles/complex-number).\nThe quotients\nqk\nare generally found by rounding the real and complex parts of the exact ratio (such as the complex number\nα/β\n) to the nearest integers. The second difference lies in the necessity of defining how one complex remainder can be \"smaller\" than another. To do this, a [norm function](https://bliptext.com/articles/norm-mathematics)\nf(u + vi) = u2 + v2\nis defined, which converts every Gaussian integer\nu + vi\ninto an ordinary integer.\nAfter each step k of the Euclidean algorithm, the norm of the remainder\nf(rk)\nis smaller than the norm of the preceding remainder,\nf(rk−1)\n. 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.\nThe final nonzero remainder is\ngcd(α, β)\n, the Gaussian integer of largest norm that divides both α and β; it is unique up to multiplication by a unit,\n±1\nor\n±i\n.\nMany of the other applications of the Euclidean algorithm carry over to Gaussian integers.\nFor 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.\n\n## Euclidean domains\nA set of elements under two [binary operations](https://bliptext.com/articles/binary-operation), denoted as addition and multiplication, is called a [Euclidean domain](https://bliptext.com/articles/euclidean-domain) if it forms a [commutative ring](https://bliptext.com/articles/commutative-ring) R and, roughly speaking, if a generalized Euclidean algorithm can be performed on them.\nThe 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](https://bliptext.com/articles/group-mathematics) or [monoid](https://bliptext.com/articles/monoid).\nNevertheless, these general operations should respect many of the laws governing ordinary arithmetic, such as [commutativity](https://bliptext.com/articles/commutative-property), [associativity](https://bliptext.com/articles/associative-property) and [distributivity](https://bliptext.com/articles/distributive-property).\nThe generalized Euclidean algorithm requires a Euclidean function, i.e., a mapping f from R into the set of nonnegative integers such that, for any two nonzero elements a and b in R, there exist q and r in R such that\na = qb + r\nand\nf(r) < f(b)\n. Examples of such mappings are the absolute value for integers, the degree for [univariate polynomials](https://bliptext.com/articles/univariate-polynomial), and the norm for Gaussian integers [above](https://bliptext.com/articles/).\nThe 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.\nThis principle relies on the [well-ordering](https://bliptext.com/articles/well-order) property of the non-negative integers, which asserts that every non-empty set of non-negative integers has a smallest member.\nThe [fundamental theorem of arithmetic](https://bliptext.com/articles/fundamental-theorem-of-arithmetic) applies to any Euclidean domain: Any number from a Euclidean domain can be factored uniquely into [irreducible elements](https://bliptext.com/articles/irreducible-element).\nAny Euclidean domain is a [unique factorization domain](https://bliptext.com/articles/unique-factorization-domain) (UFD), although the converse is not true.\nThe Euclidean domains and the UFD's are subclasses of the [GCD domains](https://bliptext.com/articles/gcd-domain), domains in which a greatest common divisor of two numbers always exists.\nIn 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.\nA Euclidean domain is always a [principal ideal domain](https://bliptext.com/articles/principal-[ideal](https://bliptext.com/articles/ideal-ring-theory)-domain) (PID), an [integral domain](https://bliptext.com/articles/integral-domain) in which every [ideal](https://bliptext.com/articles/ideal-ring-theory) is a principal [ideal](https://bliptext.com/articles/ideal-ring-theory).\nAgain, the converse is not true: not every PID is a Euclidean domain.\nThe unique factorization of Euclidean domains is useful in many applications.\nFor example, the unique factorization of the Gaussian integers is convenient in deriving formulae for all [Pythagorean triples](https://bliptext.com/articles/pythagorean-triple) and in proving [Fermat's theorem on sums of two squares](https://bliptext.com/articles/fermat-s-theorem-on-sums-of-two-squares).\nUnique factorization was also a key element in an attempted proof of [Fermat's Last Theorem](https://bliptext.com/articles/fermat-s-last-theorem) published in 1847 by Gabriel Lamé, the same mathematician who analyzed the efficiency of Euclid's algorithm, based on a suggestion of [Joseph Liouville](https://bliptext.com/articles/joseph-liouville).\nLamé's approach required the unique factorization of numbers of the form\nx + ωy\n, where x and y are integers, and\nω = e2iπ/n\nis an nth root of 1, that is,\nωn = 1\n. Although this approach succeeds for some values of n (such as\nn = 3\n, the [Eisenstein integers](https://bliptext.com/articles/eisenstein-integer)), in general such numbers do factor uniquely. This failure of unique factorization in some [cyclotomic fields](https://bliptext.com/articles/cyclotomic-field) led [Ernst Kummer](https://bliptext.com/articles/ernst-kummer) to the concept of [ideal numbers](https://bliptext.com/articles/ideal-number) and, later, [Richard Dedekind](https://bliptext.com/articles/richard-dedekind) to [ideals](https://bliptext.com/articles/ideal-ring-theory).\n\n### Unique factorization of quadratic integers\n[[File:Eisenstein primes.svg|thumb|alt=\"A set of dots lying within a circle. The pattern of dots has sixfold symmetry, i.e., rotations by 60 degrees leave the pattern unchanged. The pattern can also be mirrored about six lines passing through the center of the circle: the vertical and horizontal axes, and the four diagonal lines at ±30 and ±60 degrees.\"|Distribution of Eisenstein primes\nu + vω\nin the complex plane, with norms less than 500.\nThe number ω is a [cube root of 1](https://bliptext.com/articles/root-of-unity).]]\nThe [quadratic integer](https://bliptext.com/articles/quadratic-integer) rings are helpful to illustrate Euclidean domains.\nQuadratic integers are generalizations of the Gaussian integers in which the [imaginary unit](https://bliptext.com/articles/imaginary-unit) i is replaced by a number ω.\nThus, they have the form\nu + vω\n, 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, then\nIf, however, D does equal a multiple of four plus one, then\nIf the function f corresponds to a [norm](https://bliptext.com/articles/field-norm) function, such as that used to order the Gaussian integers [above](https://bliptext.com/articles/), then the domain is known as [norm](https://bliptext.com/articles/field-norm)-Euclidean.\nThe norm-Euclidean rings of quadratic integers are exactly those where D 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.\nThe cases\nD = −1\nand\nD = −3\nyield the [Gaussian integers](https://bliptext.com/articles/gaussian-integer) and [Eisenstein integers](https://bliptext.com/articles/eisenstein-integer), respectively.\nIf f is allowed to be any Euclidean function, then the list of possible values of D for which the domain is Euclidean is not yet known.\nThe first example of a Euclidean domain that was not norm-Euclidean (with\nD = 69\n) was published in 1994. In 1973, Weinberger proved that a quadratic integer ring with\nD > 0\nis Euclidean if, and only if, it is a [principal ideal domain](https://bliptext.com/articles/principal-ideal-domain), provided that the [generalized Riemann hypothesis](https://bliptext.com/articles/generalized-riemann-hypothesis) holds.\n\n## Noncommutative rings\nThe Euclidean algorithm may be applied to some noncommutative rings such as the set of [Hurwitz quaternions](https://bliptext.com/articles/hurwitz-quaternion).\nLet α and β represent two elements from such a ring.\nThey have a common right divisor δ if\nα = ξδ\nand\nβ = ηδ\nfor some choice of ξ and η in the ring.\nSimilarly, they have a common left divisor if\nα = dξ\nand\nβ = dη\nfor some choice of ξ and η in the ring.\nSince multiplication is not commutative, there are two versions of the Euclidean algorithm, one for right divisors and one for left divisors.\nChoosing the right divisors, the first step in finding the\ngcd(α, β)\nby the Euclidean algorithm can be written\nwhere\nψ0\nrepresents the quotient and\nρ0\nthe remainder.\nHere the quotent and remainder are chosen so that (if nonzero) the remainder has\nN(ρ0) < N(β)\nfor a \"Euclidean function\" N defined analogously to the Euclidean functions of [Euclidean domains](https://bliptext.com/articles/euclidean-domain) in the non-commutative case.\nThis equation shows that any common right divisor of α and β is likewise a common divisor of the remainder\nρ0\n. The analogous equation for the left divisors would be\nWith either choice, the process is repeated as above until the greatest common right or left divisor is identified.\nAs in the Euclidean domain, the \"size\" of the remainder\nρ0\n(formally, its Euclidean function or \"norm\") must be strictly smaller than β, and there must be only a finite number of possible sizes for\nρ0\n, so that the algorithm is guaranteed to terminate.\nMany results for the GCD carry over to noncommutative numbers.\nFor example, [Bézout's identity](https://bliptext.com/articles/b-zout-s-identity) states that the right\ngcd(α, β)\ncan be expressed as a linear combination of α and β.\nIn other words, there are numbers σ and τ such that\nThe analogous identity for the left GCD is nearly the same:\nBézout's identity can be used to solve Diophantine equations.\nFor instance, one of the standard proofs of [Lagrange's four-square theorem](https://bliptext.com/articles/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.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T16:47:46.363Z","updated_at":"2025-01-25T16:47:46.363Z","search_vector":"'algorithm':2 'euclidean':1","search_content":" \n \n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), the **Euclidean algorithm**, or **Euclid's algorithm**, is an efficient method for computing the [greatest common divisor](https://bliptext.com/articles/greatest-common-divisor) (GCD) of two [integers](https://bliptext.com/articles/integers), the largest number that divides them both without a [remainder](https://bliptext.com/articles/remainder).\nIt is named after the ancient Greek [mathematician](https://bliptext.com/articles/mathematician) [Euclid](https://bliptext.com/articles/euclid), who first described it in his Elements (c. 300 BC).\nIt is an example of an [algorithm](https://bliptext.com/articles/algorithm), a step-by-step procedure for performing a calculation according to well-defined rules,\nand is one of the oldest algorithms in common use.\nIt can be used to reduce [fractions](https://bliptext.com/articles/fraction-mathematics) to their [simplest form](https://bliptext.com/articles/irreducible-fraction), and is a part of many other number-theoretic and cryptographic calculations.\nThe Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.\nFor example, 21 is the GCD of 252 and 105 (as\nand\n, and the same number 21 is also the GCD of 105 and\n252 − 105 = 147\n. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal.\nWhen that occurs, that number is the GCD of the original two numbers.\nBy [reversing the steps](https://bliptext.com/articles/) or using the [extended Euclidean algorithm](https://bliptext.com/articles/extended-euclidean-algorithm), the GCD can be expressed as a [linear combination](https://bliptext.com/articles/linear-combination) of the two original numbers, that is the sum of the two numbers, each multiplied by an [integer](https://bliptext.com/articles/integer) (for example,\n). The fact that the GCD can always be expressed in this way is known as [Bézout's identity](https://bliptext.com/articles/b-zout-s-identity).\nThe version of the Euclidean algorithm described above—which follows Euclid's original presentation—can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other.\nA more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder).\nWith this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer.\nThis was proven by [Gabriel Lamé](https://bliptext.com/articles/gabriel-lam) in 1844 ([Lamé's Theorem](https://bliptext.com/articles/lam-s-theorem)), and marks the beginning of [computational complexity theory](https://bliptext.com/articles/computational-complexity-theory).\nAdditional methods for improving the algorithm's efficiency were developed in the 20th century.\nThe Euclidean algorithm has many theoretical and practical applications.\nIt is used for reducing [fractions](https://bliptext.com/articles/fraction-mathematics) to their [simplest form](https://bliptext.com/articles/irreducible-fraction) and for performing [division](https://bliptext.com/articles/division-mathematics) in [modular arithmetic](https://bliptext.com/articles/modular-arithmetic).\nComputations using this algorithm form part of the [cryptographic protocols](https://bliptext.com/articles/cryptographic-protocol) that are used to secure [internet](https://bliptext.com/articles/internet) communications, and in methods for breaking these cryptosystems by [factoring large composite numbers](https://bliptext.com/articles/integer-factorization).\nThe Euclidean algorithm may be used to solve [Diophantine equations](https://bliptext.com/articles/diophantine-equation), such as finding numbers that satisfy multiple congruences according to the [Chinese remainder theorem](https://bliptext.com/articles/chinese-remainder-theorem), to construct [continued fractions](https://bliptext.com/articles/simple-continued-fraction), and to find accurate [rational approximations](https://bliptext.com/articles/diophantine-approximation) to real numbers.\nFinally, it can be used as a basic tool for proving theorems in [number theory](https://bliptext.com/articles/number-theory) such as [Lagrange's four-square theorem](https://bliptext.com/articles/lagrange-s-four-square-theorem) and the [uniqueness of prime factorizations](https://bliptext.com/articles/fundamental-theorem-of-arithmetic).\nThe original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as [Gaussian integers](https://bliptext.com/articles/gaussian-integer) and [polynomials](https://bliptext.com/articles/polynomial) of one variable.\nThis led to modern [abstract algebraic](https://bliptext.com/articles/abstract-algebra) notions such as [Euclidean domains](https://bliptext.com/articles/euclidean-domain).\n# [Euclid's method for finding the greatest common divisor (GCD) of two starting lengths BA and DC, both defined to be multiples of a common \"unit\" length. The length DC being shorter, it is used to \"measure\" BA, but only once because the remainder EA is less than DC. EA now measures (twice) the shorter length DC, with remainder FC shorter than EA. Then FC measures (three times) length EA. Because there is no remainder, the process ends with FC being the GCD. On the right Nicomachus's example with numbers 49 and 21 resulting in their GCD of 7 (derived from Heath 1908:300). | upload.wikimedia.org/wikipedia/commons/e/e4////Euclid%27s///algorithm///Book///VII///Proposition///2///3.svg]\n\n# Background: greatest common divisor\nThe Euclidean algorithm calculates the greatest common divisor (GCD) of two [natural numbers](https://bliptext.com/articles/natural-number) a and b. The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder.\nSynonyms for GCD include greatest common factor (GCF), highest common factor (HCF), highest common divisor (HCD), and greatest common measure (GCM).\nThe greatest common divisor is often written as\ngcd(a, b)\nor, more simply, as\n(a, b)\n, although the latter notation is ambiguous, also used for concepts such as an [ideal](https://bliptext.com/articles/ideal-ring-theory) in the [ring of integers](https://bliptext.com/articles/ring-of-integers), which is closely related to GCD.\nIf\ngcd(a, b) = 1\n, then a and b are said to be [coprime](https://bliptext.com/articles/coprime-integers) (or relatively prime).\nThis property does not imply that a or b are themselves [prime numbers](https://bliptext.com/articles/prime-number).\nFor example, 6 and 35 factor as 6 = 2 × 3 and 35 = 5 × 7, so they are not prime, but their prime factors are different, so 6 and 35 are coprime, with no common factors other than 1.\n[[File:24x60.svg|thumb|upright|alt=\"Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall.\"|A 24×60 rectangle is covered with ten 12×12 square tiles, where 12 is the GCD of 24 and 60. More generally, an\na×b\nrectangle can be covered with square tiles of side-length c only if c is a common divisor of a and b.]]\nLet\n. Since a and b are both multiples of g, they can be written\nand, and there is no larger number\nG > g\nfor which this is true.\nThe natural numbers m and n must be coprime, since any common factor could be factored out of m and n to make g greater.\nThus, any other number c that divides both a and b must also divide g. The greatest common divisor g of a and b is the unique (positive) common divisor of a and b that is divisible by any other common divisor c.\nThe greatest common divisor can be visualized as follows.\nConsider a rectangular area a by b, and any common divisor c that divides both a and b exactly.\nThe sides of the rectangle can be divided into segments of length c, which divides the rectangle into a grid of squares of side length c. The GCD g is the largest value of c for which this is possible.\nFor illustration, a\n24×60\nrectangular area can be divided into a grid of:\n1×1\nsquares,\n2×2\nsquares,\n3×3\nsquares,\n4×4\nsquares,\n6×6\nsquares or\n12×12\nsquares.\nTherefore,\n12\nis the GCD of\n24\nand\n60\n. A\n24×60\nrectangular area can be divided into a grid of\n12×12\nsquares, with two squares along one edge (\n) and five squares along the other (\n).\nThe greatest common divisor of two numbers a and b 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 a and b. For example, since\n1386\ncan be factored into\n2 × 3 × 3 × 7 × 11\n, and\n3213\ncan be factored into\n3 × 3 × 3 × 7 × 17\n, the GCD of\n1386\nand\n3213\nequals\n, the product of their shared prime factors (with 3 repeated since\n3 × 3\ndivides both). If two numbers have no common prime factors, their GCD is\n1\n(obtained here as an instance of the [empty product](https://bliptext.com/articles/empty-product)); in other words, they are coprime.\nA key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors.\n[Factorization](https://bliptext.com/articles/integer-factorization) of large integers is believed to be a computationally very difficult problem, and the security of many widely used [cryptographic protocols](https://bliptext.com/articles/cryptographic-protocol) is based upon its infeasibility.\nAnother definition of the GCD is helpful in advanced mathematics, particularly [ring theory](https://bliptext.com/articles/ring-theory).\nThe greatest common divisor g of two nonzero numbers a and b is also their smallest positive integral linear combination, that is, the smallest positive number of the form\nua + vb\nwhere u and v are integers.\nThe set of all integral linear combinations of a and b is actually the same as the set of all multiples of g (mg, where m is an integer).\nIn modern mathematical language, the [ideal](https://bliptext.com/articles/ideal-ring-theory) generated by a and b is the [ideal](https://bliptext.com/articles/ideal-ring-theory) generated by g alone (an [ideal](https://bliptext.com/articles/ideal-ring-theory) generated by a single element is called a principal [ideal](https://bliptext.com/articles/ideal-ring-theory), and all [ideal](https://bliptext.com/articles/ideal-ring-theory)s of the integers are principal [ideal](https://bliptext.com/articles/ideal-ring-theory)s).\nSome properties of the GCD are in fact easier to see with this description, for instance the fact that any common divisor of a and b also divides the GCD (it divides both terms of\nua + vb\n). The equivalence of this GCD definition with the other definitions is described below.\nThe GCD of three or more numbers equals the product of the prime factors common to all the numbers, but it can also be calculated by repeatedly taking the GCDs of pairs of numbers.\nFor example,\ngcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b).\nThus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers.\n\n# Description\n\n## Procedure\nThe 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: with.\nThe integer r_{n-1} will then be the GCD and we can state.\nThe algorithm indicates how to construct the intermediate remainders r_k via [division-with-remainder](https://bliptext.com/articles/euclidean-division) on the preceding pair by finding an integer quotient q_k so that:\nBecause the sequence of non-negative integers \\{ r_k \\} is strictly decreasing, it eventually [must terminate](https://bliptext.com/articles/well-ordering-principle).\nIn 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.\nIn fact, the algorithm will always terminate at the n-th step with r_n equal to zero.\nTo illustrate, suppose the GCD of 1071 and 462 is requested.\nThe sequence is initially and in order to find r_0, we need to find integers q_0 and such that:\nThis is the quotient q_0 = 2 since.\nThis determines r_0 = 147 and so the sequence is now.\nThe next step is to continue the sequence to find r_1 by finding integers q_1 and r_1 b a := a − b **else**\nb := b − a **return** a\nThe variables a and b alternate holding the previous remainders rk−1 and rk−2.\nAssume that a is larger than b at the beginning of an iteration; then a equals rk−2, since rk−2 > rk−1.\nDuring the loop iteration, a is reduced by multiples of the previous remainder b until a is smaller than b.\nThen a is the next remainder rk. Then b is reduced by multiples of a until it is again smaller than a, giving the next remainder rk+1, and so on.\nThe recursive version is based on the equality of the GCDs of successive remainders and the stopping condition gcd(rN−1, 0) = rN−1.\n**function** gcd(a, b) **if** b = 0\n**return** a **else**\n**return** gcd(b, a **mod** b)\n(As above, if negative inputs are allowed, or if the **mod** function may **return** negative values, the instruction \"**return** a\" must be changed into \"**return** max(a, −a)\".)\nFor illustration, the gcd(1071, 462) is calculated from the equivalent gcd(462, 1071 mod 462) = gcd(462, 147).\nThe latter GCD is calculated from the gcd(147, 462 mod 147) = gcd(147, 21), which in turn is calculated from the gcd(21, 147 mod 21) = gcd(21, 0) = 21.\n\n## Method of least absolute remainders\nIn 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.\nPreviously, the equation\nrk−2 = qk rk−1 + rk\nassumed that\nrk−1\n. However, an alternative negative remainder\nek\ncan be computed:\nrk−2 = (qk + 1) rk−1 + ek\nif\nrk−1 > 0\nor\nrk−2 = (qk − 1) rk−1 + ek\nif\nrk−1 0, y > 0), only a finite number of solutions may be possible.\nThis 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](https://bliptext.com/articles/system-of-linear-equations) when the solutions can be any [real number](https://bliptext.com/articles/real-number) (see [Underdetermined system](https://bliptext.com/articles/underdetermined-system)).\n# [Plot of a linear Diophantine equation, 9x + 12y = 483. The solutions are shown as blue circles. | upload.wikimedia.org/wikipedia/commons/9/94/Diophante///Bezout.svg]\n\n## Multiplicative inverses and the RSA algorithm\nA [finite field](https://bliptext.com/articles/finite-field) is a set of numbers with four generalized operations.\nThe operations are called addition, subtraction, multiplication and division and have their usual properties, such as [commutativity](https://bliptext.com/articles/commutativity), [associativity](https://bliptext.com/articles/associativity) and [distributivity](https://bliptext.com/articles/distributivity).\nAn example of a finite field is the set of 13 numbers {0, 1, 2, ..., 12} using [modular arithmetic](https://bliptext.com/articles/modular-arithmetic).\nIn this field, the results of any mathematical operation (addition, subtraction, multiplication, or division) is reduced [modulo](https://bliptext.com/articles/modulo-operation) 13; that is, multiples of 13 are added or subtracted until the result is brought within the range 0–12.\nFor example, the result of 5 × 7 = 35 mod 13 = 9.\nSuch finite fields can be defined for any prime p; using more sophisticated definitions, they can also be defined for any power m of a prime pm. Finite fields are often called [Galois](https://bliptext.com/articles/variste-galois) fields, and are abbreviated as GF(p) or GF(pm).\nIn such a field with m numbers, every nonzero element a has a unique [modular multiplicative inverse](https://bliptext.com/articles/modular-multiplicative-inverse), a−1 such that aa−1 = a−1a ≡ 1 mod m. This inverse can be found by solving the congruence equation ax ≡ 1 mod m, or the equivalent linear Diophantine equation\nax + my = 1.\nThis equation can be solved by the Euclidean algorithm, as described [above](https://bliptext.com/articles/).\nFinding multiplicative inverses is an essential step in the [RSA algorithm](https://bliptext.com/articles/rsa-algorithm), which is widely used in [electronic commerce](https://bliptext.com/articles/electronic-commerce); specifically, the equation determines the integer used to decrypt the message.\nAlthough the RSA algorithm uses [rings](https://bliptext.com/articles/ring-mathematics) rather than fields, the Euclidean algorithm can still be used to find a multiplicative inverse where one exists.\nThe Euclidean algorithm also has other applications in [error-correcting codes](https://bliptext.com/articles/error-correcting-code); for example, it can be used as an alternative to the [Berlekamp–Massey algorithm](https://bliptext.com/articles/berlekamp-massey-algorithm) for decoding [BCH](https://bliptext.com/articles/bch-code) and [Reed–Solomon codes](https://bliptext.com/articles/reed-solomon-code), which are based on Galois fields.\n\n## Chinese remainder theorem\nEuclid's algorithm can also be used to solve multiple linear Diophantine equations.\nSuch equations arise in the [Chinese remainder theorem](https://bliptext.com/articles/chinese-remainder-theorem), which describes a novel method to represent an integer x.\nInstead of representing an integer by its digits, it may be represented by its remainders xi modulo a set of N coprime numbers mi:\nThe 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\nThus, each Mi is the product of all the moduli except mi. The solution depends on finding N new numbers hi such that\nWith these numbers hi, any integer x can be reconstructed from its remainders xi by the equation\nSince these numbers hi are the multiplicative inverses of the Mi, they may be found using Euclid's algorithm as described in the previous subsection.\n\n## Stern–Brocot tree\nThe Euclidean algorithm can be used to arrange the set of all positive [rational numbers](https://bliptext.com/articles/rational-number) into an infinite [binary search tree](https://bliptext.com/articles/binary-search-tree), called the [Stern–Brocot tree](https://bliptext.com/articles/stern-brocot-tree).\nThe 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.\nA 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.\nThe 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.\nThis fact can be used to prove that each positive rational number appears exactly once in this tree.\nFor example, 3/4 can be found by starting at the root, going to the left once, then to the right twice:\nThe Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called the [Calkin–Wilf tree](https://bliptext.com/articles/calkin-wilf-tree).\nThe 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.\n# [The Stern–Brocot tree, and the Stern–Brocot sequences of order i for i = 1, 2, 3, 4 | upload.wikimedia.org/wikipedia/commons/3/37/SternBrocotTree.svg]\n\n## Continued fractions\nThe Euclidean algorithm has a close relationship with [continued fractions](https://bliptext.com/articles/continued-fraction).\nThe sequence of equations can be written in the form\nThe last term on the right-hand side always equals the inverse of the left-hand side of the next equation.\nThus, the first two equations may be combined to form\nThe third equation may be used to substitute the denominator term r1/r0, yielding\nThe final ratio of remainders rk/rk−1 can always be replaced using the next equation in the series, up to the final equation.\nThe result is a continued fraction\nIn the worked example [above](https://bliptext.com/articles/), the gcd(1071, 462) was calculated, and the quotients qk were 2, 3 and 7, respectively.\nTherefore, the fraction 1071/462 may be written\nas can be confirmed by calculation.\n\n## Factorization algorithms\nCalculating a greatest common divisor is an essential step in several [integer factorization](https://bliptext.com/articles/integer-factorization) algorithms, such as [Pollard's rho algorithm](https://bliptext.com/articles/pollard-s-rho-algorithm), [Shor's algorithm](https://bliptext.com/articles/shor-s-algorithm), [Dixon's factorization method](https://bliptext.com/articles/dixon-s-factorization-method) and the [Lenstra elliptic curve factorization](https://bliptext.com/articles/lenstra-elliptic-curve-factorization).\nThe Euclidean algorithm may be used to find this GCD efficiently.\n[Continued fraction factorization](https://bliptext.com/articles/continued-fraction-factorization) uses continued fractions, which are determined using Euclid's algorithm.\n\n# Algorithmic efficiency\nThe computational efficiency of Euclid's algorithm has been studied thoroughly.\nThis efficiency can be described by the number of division steps the algorithm requires, multiplied by the computational expense of each step.\nThe first known analysis of Euclid's algorithm is due to [A. A. L. Reynaud](https://bliptext.com/articles/antoine-andr-louis-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.\nLater, in 1841, [P. J. E. Finck](https://bliptext.com/articles/pierre-joseph-tienne-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.\n[Émile Léger](https://bliptext.com/articles/mile-l-ger), in 1837, studied the worst case, which is when the inputs are consecutive [Fibonacci numbers](https://bliptext.com/articles/fibonacci-numbers).\nFinck's analysis was refined by [Gabriel Lamé](https://bliptext.com/articles/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.\nIn the [uniform cost model](https://bliptext.com/articles/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](https://bliptext.com/articles/constant-time), and Lamé's analysis implies that the total running time is also O(h).\nHowever, 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).\nIn this case the total time for all of the steps of the algorithm can be analyzed using a [telescoping series](https://bliptext.com/articles/telescoping-series), showing that it is also O(h2).\nModern algorithmic techniques based on the [Schönhage–Strassen algorithm](https://bliptext.com/articles/sch-nhage-strassen-algorithm) for fast integer multiplication can be used to speed this up, leading to [quasilinear algorithms](https://bliptext.com/articles/quasilinear-time) for the GCD.\n# [Number of steps in the Euclidean algorithm for gcd(x,y). Lighter (red and yellow) points indicate relatively few steps, whereas darker (violet and blue) points indicate more steps. The largest dark area follows the line y = Φx, where Φ is the golden ratio. | upload.wikimedia.org/wikipedia/commons/8/85/Euclidean///Algorithm///Running///Time.svg]\n\n## Number of steps\nThe number of steps to calculate the GCD of two natural numbers, a and b, may be denoted by T(a, b).\nIf g is the GCD of a and b, then a = mg and b = ng for two coprime numbers m and n.\nThen\nT(a, b) = T(m, n)\nas may be seen by dividing all the steps in the Euclidean algorithm by g.\nBy 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).\nTherefore, 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.\nThe recursive nature of the Euclidean algorithm gives another equation\nT(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1\nwhere T(x, 0) = 0 by assumption.\n\n### Worst-case\nIf 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](https://bliptext.com/articles/fibonacci-number) FN+2 and FN+1, respectively.\nMore precisely, if the Euclidean algorithm requires N steps for the pair a > b, then one has a ≥ FN+2 and b ≥ FN+1.\nThis can be shown by [induction](https://bliptext.com/articles/mathematical-induction).\nIf 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.\nNow assume that the result holds for all values of N up to M − 1.\nThe first step of the M-step algorithm is a = q0b + r0, and the Euclidean algorithm requires M − 1 steps for the pair b > r0.\nBy induction hypothesis, one has b ≥ FM+1 and r0 ≥ FM. Therefore, a = q0b + r0 ≥ b + r0 ≥ FM+1 + FM = FM+2,\nwhich is the desired inequality.\nThis proof, published by [Gabriel Lamé](https://bliptext.com/articles/gabriel-lam) in 1844, represents the beginning of [computational complexity theory](https://bliptext.com/articles/computational-complexity-theory), and also the first practical application of the Fibonacci numbers.\nThis 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).\nFor 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](https://bliptext.com/articles/golden-ratio).\nSince b ≥ φN−1, then N − 1 ≤ logφb.\nSince log10φ > 1/5, (N − 1)/5 < log10φ logφb = log10b.\nThus, N ≤ 5 log10b.\nThus, the Euclidean algorithm always needs less than O(h) divisions, where h is the number of digits in the smaller number b.\n\n### Average\nThe average number of steps taken by the Euclidean algorithm has been defined in three different ways.\nThe 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\nHowever, since T(a, b) fluctuates dramatically with the GCD of the two numbers, the averaged function T(a) is likewise \"noisy\".\nTo reduce this noise, a second average τ(a) is taken over all numbers coprime with a\nThere are φ(a) coprime integers less than a, where φ is [Euler's totient function](https://bliptext.com/articles/euler-s-totient-function).\nThis tau average grows smoothly with a\nwith the residual error being of order a−(1/6) + ε, where ε is [infinitesimal](https://bliptext.com/articles/infinitesimal).\nThe constant C in this formula is called [Porter's constant](https://bliptext.com/articles/porter-s-constant) and equals\nwhere γ is the [Euler–Mascheroni constant](https://bliptext.com/articles/euler-mascheroni-constant) and ζ' is the [derivative](https://bliptext.com/articles/derivative) of the [Riemann zeta function](https://bliptext.com/articles/riemann-zeta-function).\nThe leading coefficient (12/π2) ln 2 was determined by two independent methods.\nSince the first average can be calculated from the tau average by summing over the divisors d of a\nit can be approximated by the formula\nwhere Λ(d) is the [Mangoldt function](https://bliptext.com/articles/von-mangoldt-function).\nA 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\nSubstituting the approximate formula for T(a) into this equation yields an estimate for Y(n)\n\n## Computational expense per step\nIn 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\nrk−2 = qk rk−1 + rk.\nThe 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\nrk = rk−2 − qk rk−1.\nThe computational expense of dividing h-bit numbers scales as\nO(h(ℓ+1))\n, where ℓ is the length of the quotient.\nFor comparison, Euclid's original subtraction-based algorithm can be much slower.\nA single integer division is equivalent to the quotient q number of subtractions.\nIf the ratio of a and b is very large, the quotient is large and many subtractions will be required.\nOn the other hand, it has been shown that the quotients are very likely to be small integers.\nThe probability of a given quotient q is approximately\nln\nwhere\nu = (q + 1)2\n. 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.\nSince 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.\nThis is exploited in the [binary version](https://bliptext.com/articles/binary-gcd-algorithm) of Euclid's algorithm.\nCombining 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.\nLet\nh0, h1, ..., hN−1\nrepresent the number of digits in the successive remainders\nr0, r1, ..., rN−1\n. Since the number of steps N grows linearly with h, the running time is bounded by\n\n## Alternative methods\nEuclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity.\nFor comparison, the efficiency of alternatives to Euclid's algorithm may be determined.\nOne 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.\nThe common divisors can be found by dividing both numbers by successive integers from 2 to the smaller number b.\nThe number of steps of this approach grows linearly with b, or exponentially in the number of digits.\nAnother inefficient approach is to find the prime factors of one or both numbers.\nAs noted [above](https://bliptext.com/articles/), the GCD equals the product of the prime factors shared by the two numbers a and b.\nPresent methods for [prime factorization](https://bliptext.com/articles/integer-factorization) are also inefficient; many modern cryptography systems even rely on that inefficiency.\nThe [[binary](https://bliptext.com/articles/binary-numeral-system) GCD algorithm](https://bliptext.com/articles/[binary](https://bliptext.com/articles/binary-numeral-system)-gcd-algorithm) is an efficient alternative that substitutes division with faster operations by exploiting the [binary](https://bliptext.com/articles/binary-numeral-system) representation used by computers.\nHowever, this alternative also scales like O(h²).\nIt is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way.\nAdditional efficiency can be gleaned by examining only the leading digits of the two numbers a and b.\nThe binary algorithm can be extended to other bases (k-ary algorithms), with up to fivefold increases in speed.\n[Lehmer's GCD algorithm](https://bliptext.com/articles/lehmer-s-gcd-algorithm) uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases.\nA recursive approach for very large integers (with more than 25,000 digits) leads to [quasilinear](https://bliptext.com/articles/quasilinear-time) integer GCD algorithms, such as those of Schönhage, and Stehlé and Zimmermann.\nThese algorithms exploit the 2×2 matrix form of the Euclidean algorithm given [above](https://bliptext.com/articles/).\nThese quasilinear methods generally scale as\nO(h log h2 log log h).\n\n# Generalizations\nAlthough 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](https://bliptext.com/articles/polynomial), [quadratic integers](https://bliptext.com/articles/quadratic-integer) and [Hurwitz quaternions](https://bliptext.com/articles/hurwitz-quaternion).\nIn the latter cases, the Euclidean algorithm is used to demonstrate the crucial property of unique factorization, i.e., that such numbers can be factored uniquely into [irreducible elements](https://bliptext.com/articles/irreducible-element), the counterparts of prime numbers.\nUnique factorization is essential to many proofs of number theory.\n\n## Rational and real numbers\nEuclid's algorithm can be applied to [real numbers](https://bliptext.com/articles/real-number), as described by Euclid in Book 10 of his [Elements](https://bliptext.com/articles/euclid-s-elements).\nThe 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:\na = mg\nand\nb = ng\n, where m and n are [integers](https://bliptext.com/articles/integer).\nThis identification is equivalent to finding an [integer relation](https://bliptext.com/articles/integer-relation-algorithm) among the real numbers a and b; that is, it determines integers s and t such that\nsa + tb = 0\n. If such an equation is possible, a and b are called commensurable lengths, otherwise they are [incommensurable lengths](https://bliptext.com/articles/commensurability-mathematics).\nThe real-number Euclidean algorithm differs from its integer counterpart in two respects.\nFirst, the remainders\nrk\nare real numbers, although the quotients\nqk\nare integers as before.\nSecond, the algorithm is not guaranteed to end in a finite number N of steps.\nIf it does, the fraction\na/b\nis a rational number, i.e., the ratio of two integers\nand can be written as a finite continued fraction\n[q0; q1, q2, ..., qN]\n. If the algorithm does not stop, the fraction\na/b\nis an [irrational number](https://bliptext.com/articles/irrational-number) and can be described by an infinite continued fraction\n[q0; q1, q2, …]\n. Examples of infinite continued fractions are the [golden ratio](https://bliptext.com/articles/golden-ratio)\nφ = [1; 1, 1, ...]\nand the [square root of two](https://bliptext.com/articles/square-root-of-2),\n√2 = [1; 2, 2, ...]\n. The algorithm is unlikely to stop, since [almost all](https://bliptext.com/articles/almost-all) ratios\na/b\nof two real numbers are irrational.\nAn infinite continued fraction may be truncated at a step\nk [q0; q1, q2, ..., qk]\nto yield an approximation to\na/b\nthat improves as k is increased.\nThe approximation is described by [convergents](https://bliptext.com/articles/convergent-continued-fraction)\nmk/nk\nwhere\nm−1 = n−2 = 1\nand\nm−2 = n−1 = 0\nare the initial values of the recursion.\nThe convergent\nmk/nk\nis the best [rational number](https://bliptext.com/articles/rational-number) approximation to\na/b\nwith denominator\nnk\n\n## Polynomials\nPolynomials in a single variable x can be added, multiplied and factored into [irreducible polynomials](https://bliptext.com/articles/irreducible-polynomial), which are the analogs of the prime numbers for integers.\nThe greatest common divisor polynomial\ng(x)\nof two polynomials\na(x)\nand\nb(x)\nis defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm.\nThe basic procedure is similar to that for integers.\nAt each step k, a quotient polynomial\nqk(x)\nand a remainder polynomial\nrk(x)\nare identified to satisfy the recursive equation\nwhere\nr−2(x) = a(x)\nand\nr−1(x) = b(x)\n. 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:\ndeg[rk(x)] < deg[rk−1(x)]\n. Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps.\nThe last nonzero remainder is the greatest common divisor of the original two polynomials,\na(x)\nand\nb(x)\n.\nFor example, consider the following two quartic polynomials, which each factor into two quadratic polynomials\n[Dividing](https://bliptext.com/articles/polynomial-long-division)\na(x)\nby\nb(x)\nyields a remainder\nr0(x) = x3 + (2/3)x2 + (5/3)x − (2/3)\n. In the next step,\nb(x)\nis divided by\nr0(x)\nyielding a remainder\nr1(x) = x2 + x + 2\n. Finally, dividing\nr0(x)\nby\nr1(x)\nyields a zero remainder, indicating that\nr1(x)\nis the greatest common divisor polynomial of\na(x)\nand\nb(x)\n, consistent with their factorization.\nMany of the applications described above for integers carry over to polynomials.\nThe Euclidean algorithm can be used to solve linear Diophantine equations and Chinese remainder problems for polynomials; continued fractions of polynomials can also be defined.\nThe polynomial Euclidean algorithm has other applications, such as [Sturm chains](https://bliptext.com/articles/sturm-chain), a method for counting the [zeros of a polynomial](https://bliptext.com/articles/zero-of-a-function) that lie inside a given [real interval](https://bliptext.com/articles/interval-mathematics).\nThis in turn has applications in several areas, such as the [Routh–Hurwitz stability criterion](https://bliptext.com/articles/routh-hurwitz-stability-criterion) in [control theory](https://bliptext.com/articles/control-theory).\nFinally, the coefficients of the polynomials need not be drawn from integers, real numbers or even the complex numbers.\nFor example, the coefficients may be drawn from a general field, such as the finite fields\nGF(p)\ndescribed above.\nThe corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.\n\n## Gaussian integers\n[[File:Gaussian primes.png|thumb|alt=\"A set of dots lying within a circle. The pattern of dots has fourfold symmetry, i.e., rotations by 90 degrees leave the pattern unchanged. The pattern can also be mirrored about four lines passing through the center of the circle: the vertical and horizontal axes, and the two diagonal lines at ±45 degrees.\"|Distribution of Gaussian primes\nu + vi\nin the complex plane, with norms\nu2 + v2\nless than 500]]\nThe [Gaussian integers](https://bliptext.com/articles/gaussian-integer) are [complex numbers](https://bliptext.com/articles/complex-number) of the form\nα = u + vi\n, where u and v are ordinary [integers](https://bliptext.com/articles/integer) and i is the [square root of negative one](https://bliptext.com/articles/imaginary-unit).\nBy defining an analog of the Euclidean algorithm, Gaussian integers can be shown to be uniquely factorizable, by the argument [above](https://bliptext.com/articles/).\nThis unique factorization is helpful in many applications, such as deriving all [Pythagorean triples](https://bliptext.com/articles/pythagorean-triple) or proving [Fermat's theorem on sums of two squares](https://bliptext.com/articles/fermat-s-theorem-on-sums-of-two-squares).\nIn general, the Euclidean algorithm is convenient in such applications, but not essential; for example, the theorems can often be proven by other arguments.\nThe Euclidean algorithm developed for two Gaussian integers α and β is nearly the same as that for ordinary integers, but differs in two respects.\nAs before, we set\nr−2 = α\nand\nr−1 = β\n, and the task at each step k is to identify a quotient\nqk\nand a remainder\nrk\nsuch that\nwhere every remainder is strictly smaller than its predecessor:\n<\n. The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are [complex numbers](https://bliptext.com/articles/complex-number).\nThe quotients\nqk\nare generally found by rounding the real and complex parts of the exact ratio (such as the complex number\nα/β\n) to the nearest integers. The second difference lies in the necessity of defining how one complex remainder can be \"smaller\" than another. To do this, a [norm function](https://bliptext.com/articles/norm-mathematics)\nf(u + vi) = u2 + v2\nis defined, which converts every Gaussian integer\nu + vi\ninto an ordinary integer.\nAfter each step k of the Euclidean algorithm, the norm of the remainder\nf(rk)\nis smaller than the norm of the preceding remainder,\nf(rk−1)\n. 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.\nThe final nonzero remainder is\ngcd(α, β)\n, the Gaussian integer of largest norm that divides both α and β; it is unique up to multiplication by a unit,\n±1\nor\n±i\n.\nMany of the other applications of the Euclidean algorithm carry over to Gaussian integers.\nFor 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.\n\n## Euclidean domains\nA set of elements under two [binary operations](https://bliptext.com/articles/binary-operation), denoted as addition and multiplication, is called a [Euclidean domain](https://bliptext.com/articles/euclidean-domain) if it forms a [commutative ring](https://bliptext.com/articles/commutative-ring) R and, roughly speaking, if a generalized Euclidean algorithm can be performed on them.\nThe 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](https://bliptext.com/articles/group-mathematics) or [monoid](https://bliptext.com/articles/monoid).\nNevertheless, these general operations should respect many of the laws governing ordinary arithmetic, such as [commutativity](https://bliptext.com/articles/commutative-property), [associativity](https://bliptext.com/articles/associative-property) and [distributivity](https://bliptext.com/articles/distributive-property).\nThe generalized Euclidean algorithm requires a Euclidean function, i.e., a mapping f from R into the set of nonnegative integers such that, for any two nonzero elements a and b in R, there exist q and r in R such that\na = qb + r\nand\nf(r) < f(b)\n. Examples of such mappings are the absolute value for integers, the degree for [univariate polynomials](https://bliptext.com/articles/univariate-polynomial), and the norm for Gaussian integers [above](https://bliptext.com/articles/).\nThe 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.\nThis principle relies on the [well-ordering](https://bliptext.com/articles/well-order) property of the non-negative integers, which asserts that every non-empty set of non-negative integers has a smallest member.\nThe [fundamental theorem of arithmetic](https://bliptext.com/articles/fundamental-theorem-of-arithmetic) applies to any Euclidean domain: Any number from a Euclidean domain can be factored uniquely into [irreducible elements](https://bliptext.com/articles/irreducible-element).\nAny Euclidean domain is a [unique factorization domain](https://bliptext.com/articles/unique-factorization-domain) (UFD), although the converse is not true.\nThe Euclidean domains and the UFD's are subclasses of the [GCD domains](https://bliptext.com/articles/gcd-domain), domains in which a greatest common divisor of two numbers always exists.\nIn 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.\nA Euclidean domain is always a [principal [ideal](https://bliptext.com/articles/ideal-ring-theory) domain](https://bliptext.com/articles/principal-[ideal](https://bliptext.com/articles/ideal-ring-theory)-domain) (PID), an [integral domain](https://bliptext.com/articles/integral-domain) in which every [ideal](https://bliptext.com/articles/ideal-ring-theory) is a principal [ideal](https://bliptext.com/articles/ideal-ring-theory).\nAgain, the converse is not true: not every PID is a Euclidean domain.\nThe unique factorization of Euclidean domains is useful in many applications.\nFor example, the unique factorization of the Gaussian integers is convenient in deriving formulae for all [Pythagorean triples](https://bliptext.com/articles/pythagorean-triple) and in proving [Fermat's theorem on sums of two squares](https://bliptext.com/articles/fermat-s-theorem-on-sums-of-two-squares).\nUnique factorization was also a key element in an attempted proof of [Fermat's Last Theorem](https://bliptext.com/articles/fermat-s-last-theorem) published in 1847 by Gabriel Lamé, the same mathematician who analyzed the efficiency of Euclid's algorithm, based on a suggestion of [Joseph Liouville](https://bliptext.com/articles/joseph-liouville).\nLamé's approach required the unique factorization of numbers of the form\nx + ωy\n, where x and y are integers, and\nω = e2iπ/n\nis an nth root of 1, that is,\nωn = 1\n. Although this approach succeeds for some values of n (such as\nn = 3\n, the [Eisenstein integers](https://bliptext.com/articles/eisenstein-integer)), in general such numbers do factor uniquely. This failure of unique factorization in some [cyclotomic fields](https://bliptext.com/articles/cyclotomic-field) led [Ernst Kummer](https://bliptext.com/articles/ernst-kummer) to the concept of [ideal numbers](https://bliptext.com/articles/ideal-number) and, later, [Richard Dedekind](https://bliptext.com/articles/richard-dedekind) to [ideals](https://bliptext.com/articles/ideal-ring-theory).\n\n### Unique factorization of quadratic integers\n[[File:Eisenstein primes.svg|thumb|alt=\"A set of dots lying within a circle. The pattern of dots has sixfold symmetry, i.e., rotations by 60 degrees leave the pattern unchanged. The pattern can also be mirrored about six lines passing through the center of the circle: the vertical and horizontal axes, and the four diagonal lines at ±30 and ±60 degrees.\"|Distribution of Eisenstein primes\nu + vω\nin the complex plane, with norms less than 500.\nThe number ω is a [cube root of 1](https://bliptext.com/articles/root-of-unity).]]\nThe [quadratic integer](https://bliptext.com/articles/quadratic-integer) rings are helpful to illustrate Euclidean domains.\nQuadratic integers are generalizations of the Gaussian integers in which the [imaginary unit](https://bliptext.com/articles/imaginary-unit) i is replaced by a number ω.\nThus, they have the form\nu + vω\n, 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, then\nIf, however, D does equal a multiple of four plus one, then\nIf the function f corresponds to a [norm](https://bliptext.com/articles/field-norm) function, such as that used to order the Gaussian integers [above](https://bliptext.com/articles/), then the domain is known as [norm](https://bliptext.com/articles/field-norm)-Euclidean.\nThe norm-Euclidean rings of quadratic integers are exactly those where D 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.\nThe cases\nD = −1\nand\nD = −3\nyield the [Gaussian integers](https://bliptext.com/articles/gaussian-integer) and [Eisenstein integers](https://bliptext.com/articles/eisenstein-integer), respectively.\nIf f is allowed to be any Euclidean function, then the list of possible values of D for which the domain is Euclidean is not yet known.\nThe first example of a Euclidean domain that was not norm-Euclidean (with\nD = 69\n) was published in 1994. In 1973, Weinberger proved that a quadratic integer ring with\nD > 0\nis Euclidean if, and only if, it is a [principal ideal domain](https://bliptext.com/articles/principal-ideal-domain), provided that the [generalized Riemann hypothesis](https://bliptext.com/articles/generalized-riemann-hypothesis) holds.\n\n## Noncommutative rings\nThe Euclidean algorithm may be applied to some noncommutative rings such as the set of [Hurwitz quaternions](https://bliptext.com/articles/hurwitz-quaternion).\nLet α and β represent two elements from such a ring.\nThey have a common right divisor δ if\nα = ξδ\nand\nβ = ηδ\nfor some choice of ξ and η in the ring.\nSimilarly, they have a common left divisor if\nα = dξ\nand\nβ = dη\nfor some choice of ξ and η in the ring.\nSince multiplication is not commutative, there are two versions of the Euclidean algorithm, one for right divisors and one for left divisors.\nChoosing the right divisors, the first step in finding the\ngcd(α, β)\nby the Euclidean algorithm can be written\nwhere\nψ0\nrepresents the quotient and\nρ0\nthe remainder.\nHere the quotent and remainder are chosen so that (if nonzero) the remainder has\nN(ρ0) < N(β)\nfor a \"Euclidean function\" N defined analogously to the Euclidean functions of [Euclidean domains](https://bliptext.com/articles/euclidean-domain) in the non-commutative case.\nThis equation shows that any common right divisor of α and β is likewise a common divisor of the remainder\nρ0\n. The analogous equation for the left divisors would be\nWith either choice, the process is repeated as above until the greatest common right or left divisor is identified.\nAs in the Euclidean domain, the \"size\" of the remainder\nρ0\n(formally, its Euclidean function or \"norm\") must be strictly smaller than β, and there must be only a finite number of possible sizes for\nρ0\n, so that the algorithm is guaranteed to terminate.\nMany results for the GCD carry over to noncommutative numbers.\nFor example, [Bézout's identity](https://bliptext.com/articles/b-zout-s-identity) states that the right\ngcd(α, β)\ncan be expressed as a linear combination of α and β.\nIn other words, there are numbers σ and τ such that\nThe analogous identity for the left GCD is nearly the same:\nBézout's identity can be used to solve Diophantine equations.\nFor instance, one of the standard proofs of [Lagrange's four-square theorem](https://bliptext.com/articles/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.","revisionCount":0},"hasMore":false,"nextCursor":null}

History