This article is about an algorithm for the greatest common divisor. For the mathematics of space, seeEuclidean geometry. For other uses of "Euclidean", seeEuclidean (disambiguation).
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 rightNicomachus's example with numbers 49 and 21 resulting in their GCD of 7 (derived from Heath 1908:300).
The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example,21 is the GCD of252 and105 (as252 = 21 × 12 and105 = 21 × 5), and the same number21 is also the GCD of105 and252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, that number is the GCD of the original two numbers. Byreversing the steps or using theextended Euclidean algorithm, the GCD can be expressed as alinear combination of the two original numbers, that is the sum of the two numbers, each multiplied by aninteger (for example,21 = 5 × 105 + (−2) × 252). The fact that the GCD can always be expressed in this way is known asBézout's identity.
The version of the Euclidean algorithm described above—which follows Euclid's original presentation—may require many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven byGabriel Lamé in 1844 (Lamé's Theorem),[1][2] and marks the beginning ofcomputational complexity theory. Additional methods for improving the algorithm's efficiency were developed in the 20th century.
The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such asGaussian integers andpolynomials of one variable. This led to modernabstract algebraic notions such asEuclidean domains.
The Euclidean algorithm calculates the greatest common divisor (GCD) of twonatural numbersa andb. The greatest common divisorg is the largest natural number that divides botha andb without leaving a remainder. Synonyms for GCD includegreatest common factor (GCF),highest common factor (HCF),highest common divisor (HCD), andgreatest common measure (GCM). The greatest common divisor is often written asgcd(a,b) or, more simply, as(a,b),[3] although the latter notation is ambiguous, also used for concepts such as anideal in thering of integers, which is closely related to GCD.
Ifgcd(a,b) = 1, thena andb are said to becoprime (or relatively prime).[4] This property does not imply thata orb are themselvesprime numbers.[5] For example,6 and35 factor as6 = 2 × 3 and35 = 5 × 7, so they are not prime, but their prime factors are different, so6 and35 are coprime, with no common factors other than 1.
A 24×60 rectangle is covered with ten 12×12 square tiles, where 12 is the GCD of 24 and 60. More generally, ana×b rectangle can be covered with square tiles of side-lengthc only ifc is a common divisor ofa andb.
Letg = gcd(a,b). Sincea andb are both multiples ofg, they can be writtena =mg andb =ng, and there is no larger numberG >g for which this is true. The natural numbersm andn must be coprime, since any common factor could be factored out ofm andn to makeg greater. Thus, any other numberc that divides botha andb must also divideg. The greatest common divisorg ofa andb is the unique (positive) common divisor ofa andb that is divisible by any other common divisorc.[6]
The greatest common divisor can be visualized as follows.[7] Consider a rectangular areaa byb, and any common divisorc that divides botha andb exactly. The sides of the rectangle can be divided into segments of lengthc, which divides the rectangle into a grid of squares of side lengthc. The GCDg is the largest value ofc for which this is possible. For illustration, a24×60 rectangular area can be divided into a grid of:1×1 squares,2×2 squares,3×3 squares,4×4 squares,6×6 squares or12×12 squares. Therefore,12 is the GCD of24 and60. A24×60 rectangular area can be divided into a grid of12×12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5).
The greatest common divisor of two numbersa andb 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 botha andb.[8] For example, since1386 can be factored into2 × 3 × 3 × 7 × 11, and3213 can be factored into3 × 3 × 3 × 7 × 17, the GCD of1386 and3213 equals63 = 3 × 3 × 7, the product of their shared prime factors (with 3 repeated since3 × 3 divides both). If two numbers have no common prime factors, their GCD is1 (obtained here as an instance of theempty product); in other words, they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors.[9][10]Factorization of large integers is believed to be a computationally very difficult problem, and the security of many widely usedcryptographic protocols is based upon its infeasibility.[11]
Another definition of the GCD is helpful in advanced mathematics, particularlyring theory.[12] The greatest common divisorg of two nonzero numbersa andb is also their smallest positive integral linear combination, that is, the smallest positive number of the formua +vb whereu andv are integers. The set of all integral linear combinations ofa andb is actually the same as the set of all multiples ofg (mg, wherem is an integer). In modern mathematical language, theideal generated bya andb is the ideal generated by g alone (an ideal generated by a single element is called aprincipal ideal, and all ideals of the integers are principal ideals). Some properties of the GCD are in fact easier to see with this description, for instance the fact that any common divisor ofa andb also divides the GCD (it divides both terms ofua + vb). The equivalence of this GCD definition with the other definitions is described below.
The GCD of three or more numbers equals the product of the prime factors common to all the numbers,[13] but it can also be calculated by repeatedly taking the GCDs of pairs of numbers.[14] For example,
= q0 × + r0 q0 =; r0 = Sincer0 = 0 the algorithm is finished. ThusGCD(, ) =. = q1 × + r1 q1 =; r1 = Sincer1 = 0 the algorithm is finished. ThusGCD(, ) =. = q2 × + r2 q2 =; r2 = Sincer2 = 0 the algorithm is finished. ThusGCD(, ) =. = q3 × + r3 q3 =; r3 = Sincer3 = 0 the algorithm is finished. ThusGCD(, ) =. = q4 × + r4 q4 =; r4 = Sincer4 = 0 the algorithm is finished. ThusGCD(, ) =. = q5 × + r5 q5 =; r5 = Sincer5 = 0 the algorithm is finished. ThusGCD(, ) =. = q6 × + r6 q6 =; r6 = Sincer6 = 0 the algorithm is finished. ThusGCD(, ) =. = q7 × + r7 q7 =; r7 = Sincer7 = 0 the algorithm is finished. ThusGCD(, ) =. = q8 × + r8 q8 =; r8 = Sincer8 = 0 the algorithm is finished. ThusGCD(, ) =. = q9 × + r9 q9 =; r9 = Sincer9 = 0 the algorithm is finished. ThusGCD(, ) =. = q10 × + r10 q10 =; r10 = Sincer10 = 0 the algorithm is finished. ThusGCD(, ) =.Number is too big for the calculator
RestartStart
The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers and and will eventually terminate with the integer zero: with The integer will then be the GCD and we can state The algorithm indicates how to construct the intermediate remainders viadivision-with-remainder on the preceding pair by finding an integer quotient so that:
Because the sequence of non-negative integers is strictly decreasing, it eventuallymust terminate. In other words, since for every and each is an integer that is strictly smaller than the preceding there eventually cannot be a non-negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at thenth step with equal to zero.[15]
To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially and in order to find we need to find integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is completed as as no further non-negative integer smaller than can be found. The penultimate remainder is therefore the requested GCD:
We can generalize slightly by dropping any ordering requirement on the initial two values and If the algorithm may continue and trivially find that as the sequence of remainders will be If then we can also continue since suggesting the next remainder should be itself, and the sequence is Normally, this would be invalid because it breaks the requirement but now we have by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy and everything continues as above. The only modifications that need to be made are that only for and that the sub-sequence of non-negative integers for is strictly decreasing, therefore excluding from both statements.
The validity of the Euclidean algorithm can be proven by a two-step argument.[16] In the first step, the final nonzero remainderrN−1 is shown to divide botha and b. Since it is a common divisor, it must be less than or equal to the greatest common divisor g. In the second step, it is shown that any common divisor ofa andb, including g, must dividerN−1; therefore,g must be less than or equal torN−1. These two opposite inequalities implyrN−1 =g.
To demonstrate thatrN−1 divides botha andb (the first step),rN−1 divides its predecessorrN−2
rN−2 =qNrN−1
since the final remainderrN is zero.rN−1 also divides its next predecessorrN−3
rN−3 =qN−1rN−2 +rN−1
because it divides both terms on the right-hand side of the equation. Iterating the same argument,rN−1 divides all the preceding remainders, includinga andb. None of the preceding remaindersrN−2,rN−3, etc. dividea andb, since they leave a remainder. SincerN−1 is a common divisor ofa and b,rN−1 ≤g.
In the second step, any natural numberc that divides botha andb (in other words, any common divisor ofa andb) divides the remaindersrk. By definition,a andb can be written as multiples ofc:a =mc andb =nc, wherem andn are natural numbers. Therefore,c divides the initial remainderr0, sincer0 =a −q0b =mc −q0nc = (m −q0n)c. An analogous argument shows thatc also divides the subsequent remaindersr1,r2, etc. Therefore, the greatest common divisorg must dividerN−1, which implies thatg ≤rN−1. Since the first part of the argument showed the reverse (rN−1 ≤g), it follows thatg =rN−1. Thus,g is the greatest common divisor of all the succeeding pairs:[17][18]
Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensionsa = 1071 andb = 462. Squares of size462×462 are placed within it leaving a462×147 rectangle. This rectangle is tiled with147×147 squares until a21×147 rectangle is left, which in turn is tiled with21×21 squares, leaving no uncovered area. The smallest square size,21, is the GCD of1071 and462.
For illustration, the Euclidean algorithm can be used to find the greatest common divisor ofa = 1071 andb = 462. To begin, multiples of462 are subtracted from1071 until the remainder is less than462. Two such multiples can be subtracted (q0 = 2), leaving a remainder of147:
1071 = 2 × 462 + 147.
Then multiples of147 are subtracted from462 until the remainder is less than147. Three multiples can be subtracted (q1 = 3), leaving a remainder of21:
462 = 3 × 147 + 21.
Then multiples of21 are subtracted from147 until the remainder is less than21. Seven multiples can be subtracted (q2 = 7), leaving no remainder:
147 = 7 × 21 + 0.
Since the last remainder is zero, the algorithm ends with21 as the greatest common divisor of1071 and462. This agrees with thegcd(1071, 462) found by prime factorizationabove. In tabular form, the steps are:
The Euclidean algorithm can be visualized in terms of the tiling analogy given above for the greatest common divisor.[19] Assume that we wish to cover ana×b rectangle with square tiles exactly, wherea is the larger of the two numbers. We first attempt to tile the rectangle usingb×b square tiles; however, this leaves anr0×b residual rectangle untiled, wherer0 <b. We then attempt to tile the residual rectangle withr0×r0 square tiles. This leaves a second residual rectangler1×r0, which we attempt to tile usingr1×r1 square tiles, and so on. The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the previous residual rectangle exactly. The length of the sides of the smallest square tile is the GCD of the dimensions of the original rectangle. For example, the smallest square tile in the adjacent figure is21×21 (shown in red), and21 is the GCD of1071 and462, the dimensions of the original rectangle (shown in green).
At every stepk, the Euclidean algorithm computes a quotientqk and remainderrk from two numbersrk−1 andrk−2
rk−2 =qkrk−1 +rk,
where therk is non-negative and is strictly less than theabsolute value ofrk−1. The theorem which underlies the definition of theEuclidean division ensures that such a quotient and remainder always exist and are unique.[20]
In Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is,rk−1 is subtracted fromrk−2 repeatedly until the remainderrk is smaller thanrk−1. After thatrk andrk−1 are exchanged and the process is iterated. Euclidean division reduces all the steps between two exchanges into a single step, which is thus more efficient. Moreover, the quotients are not needed, thus one may replace Euclidean division by themodulo operation, which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply
Implementations of the algorithm may be expressed inpseudocode. For example, the division-based version may beprogrammed as[21]
function gcd(a, b)while b ≠ 0 t := b b := amod b a := treturn a
At the beginning of thekth iteration, the variableb holds the latest remainderrk−1, whereas the variablea holds its predecessor,rk−2. The stepb :=a modb is equivalent to the above recursion formulark ≡rk−2 modrk−1. Thetemporary variablet holds the value ofrk−1 while the next remainderrk is being calculated. At the end of the loop iteration, the variableb holds the remainderrk, whereas the variablea holds its predecessor,rk−1.
(If negative inputs are allowed, or if themod function may return negative values, the last line must be replaced withreturn abs(a).)
In the subtraction-based version, which was Euclid's original version, the remainder calculation (b := amod b) is replaced by repeated subtraction.[22] Contrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops whena =b:
function gcd(a, b)while a ≠ bif a > b a := a − belse b := b − areturn a
The variablesa andb alternate holding the previous remaindersrk−1 andrk−2. Assume thata is larger thanb at the beginning of an iteration; thena equalsrk−2, sincerk−2 >rk−1. During the loop iteration,a is reduced by multiples of the previous remainderb untila is smaller thanb. Thena is the next remainderrk. Thenb is reduced by multiples ofa until it is again smaller thana, giving the next remainderrk+1, and so on.
The recursive version[23] is based on the equality of the GCDs of successive remainders and the stopping conditiongcd(rN−1, 0) =rN−1.
function gcd(a, b)if b = 0return aelsereturn gcd(b, amod b)
(As above, if negative inputs are allowed, or if themod function may return negative values, the instructionreturn a must be replaced byreturn max(a, −a).)
For illustration, thegcd(1071, 462) is calculated from the equivalentgcd(462, 1071 mod 462) = gcd(462, 147). The latter GCD is calculated from thegcd(147, 462 mod 147) = gcd(147, 21), which in turn is calculated from thegcd(21, 147 mod 21) = gcd(21, 0) = 21.
In another version of Euclid's algorithm, the quotient at each step is increased by one if the resulting negative remainder is smaller in magnitude than the typical positive remainder.[24][25] Previously, the equation
rk−2 =qkrk−1 +rk
assumed that|rk−1| >rk > 0. However, an alternative negative remainderek can be computed:
rk−2 = (qk + 1)rk−1 +ek
ifrk−1 > 0 or
rk−2 = (qk – 1)rk−1 +ek
ifrk−1 < 0.
Ifrk is replaced byek. when|ek| < |rk|, then one gets a variant of Euclidean algorithm such that
|rk| ≤ |rk−1| / 2
at each step.
Leopold Kronecker has shown that this version requires the fewest steps of any version of Euclid's algorithm.[24][25] More generally, it has been proven that, for every input numbersa andb, the number of steps is minimal if and only ifqk is chosen in order that where is thegolden ratio.[26]
The Euclidean algorithm was probably invented beforeEuclid, depicted here holding acompass in a painting of about 1474.
The Euclidean algorithm is one of the oldest algorithms in common use.[27] It appears inEuclid'sElements (c. 300 BC), specifically in Book 7 (Propositions 1–2) and Book 10 (Propositions 2–3). In Book 7, the algorithm is formulated for integers, whereas in Book 10, it is formulated for lengths of line segments. (In modern usage, one would say it was formulated there forreal numbers. But lengths, areas, and volumes, represented as real numbers in modern usage, are not measured in the same units and there is no natural unit of length, area, or volume; the concept of real numbers was unknown at that time.) The latter algorithm is geometrical. The GCD of two lengthsa andb corresponds to the greatest lengthg that measuresa andb evenly; in other words, the lengthsa andb are both integer multiples of the lengthg.
The algorithm was probably not discovered byEuclid, who compiled results from earlier mathematicians in hisElements.[28][29] The mathematician and historianB. L. van der Waerden suggests that Book VII derives from a textbook onnumber theory written by mathematicians in the school ofPythagoras.[30] The algorithm was probably known byEudoxus of Cnidus (about 375 BC).[27][31] The algorithm may even pre-date Eudoxus,[32][33] judging from the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid andAristotle.[34] Claude Brezinski, following remarks byPappus of Alexandria, credits the algorithm toTheaetetus (c. 417 – c. 369 BC).[35]
Centuries later, Euclid's algorithm was discovered independently both in India and in China,[36] primarily to solveDiophantine equations that arose in astronomy and making accurate calendars. In the late 5th century, the Indian mathematician and astronomerAryabhata described the algorithm as the "pulverizer",[37] perhaps because of its effectiveness in solving Diophantine equations.[38] Although a special case of theChinese remainder theorem had already been described in the Chinese bookSunzi Suanjing,[39] the general solution was published byQin Jiushao in his 1247 bookShushu Jiuzhang (數書九章Mathematical Treatise in Nine Sections).[40] The Euclidean algorithm was first describednumerically and popularized in Europe in the second edition ofBachet'sProblèmes plaisants et délectables (Pleasant and enjoyable problems, 1624).[37] In Europe, it was likewise used to solve Diophantine equations and in developingcontinued fractions. Theextended Euclidean algorithm was published by the English mathematicianNicholas Saunderson,[41] who attributed it toRoger Cotes as a method for computing continued fractions efficiently.[42]
In the 19th century, the Euclidean algorithm led to the development of new number systems, such asGaussian integers andEisenstein integers. In 1815,Carl Gauss used the Euclidean algorithm to demonstrate unique factorization ofGaussian integers, although his work was first published in 1832.[43] Gauss mentioned the algorithm in hisDisquisitiones Arithmeticae (published 1801), but only as a method forcontinued fractions.[36]Peter Gustav Lejeune Dirichlet seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory.[44] Lejeune Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied.[45] Lejeune Dirichlet's lectures on number theory were edited and extended byRichard Dedekind, who used Euclid's algorithm to studyalgebraic integers, a new general type of number. For example, Dedekind was the first to proveFermat's two-square theorem using the unique factorization of Gaussian integers.[46] Dedekind also defined the concept of aEuclidean domain, a number system in which a generalized version of the Euclidean algorithm can be defined (as describedbelow). In the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory ofideals.[47]
"[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day."
Donald Knuth,The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd edition (1981), p. 318.
Other applications of Euclid's algorithm were developed in the 19th century. In 1829,Charles Sturm showed that the algorithm was useful in theSturm chain method for counting the real roots of polynomials in any given interval.[48]
In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, calledThe Game of Euclid,[52] which has an optimal strategy.[53] The players begin with two piles ofa andb stones. The players take turns removingm multiples of the smaller pile from the larger. Thus, if the two piles consist ofx andy stones, wherex is larger thany, the next player can reduce the larger pile fromx stones tox −my stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.[54][55]
Bézout's identity states that the greatest common divisorg of two integersa andb can be represented as a linear sum of the original two numbersa andb.[56] In other words, it is always possible to find integerss andt such thatg =sa +tb.[57][58]
The integerss andt can be calculated from the quotientsq0,q1, etc. by reversing the order of equations in Euclid's algorithm.[59] Beginning with the next-to-last equation,g can be expressed in terms of the quotientqN−1 and the two preceding remainders,rN−2 andrN−3:
g =rN−1 =rN−3 −qN−1rN−2.
Those two remainders can be likewise expressed in terms of their quotients and preceding remainders,
rN−2 =rN−4 −qN−2rN−3 and
rN−3 =rN−5 −qN−3rN−4.
Substituting these formulae forrN−2 andrN−3 into the first equation yieldsg as a linear sum of the remaindersrN−4 andrN−5. The process of substituting remainders by formulae involving their predecessors can be continued until the original numbersa andb are reached:
r2 =r0 −q2r1
r1 =b −q1r0
r0 =a −q0b.
After all the remaindersr0,r1, etc. have been substituted, the final equation expressesg as a linear sum ofa andb, so thatg =sa +tb.
The Euclidean algorithm, and thus Bézout's identity, can be generalized to the context ofEuclidean domains.
Bézout's identity provides yet another definition of the greatest common divisorg of two numbersa andb.[12] Consider the set of all numbersua +vb, whereu andv are any two integers. Sincea andb are both divisible byg, every number in the set is divisible byg. In other words, every number of the set is an integer multiple ofg. This is true for every common divisor ofa andb. However, unlike other common divisors, the greatest common divisor is a member of the set; by Bézout's identity, choosingu =s andv =t givesg. A smaller common divisor cannot be a member of the set, since every member of the set must be divisible byg. Conversely, any multiplem ofg can be obtained by choosingu =ms andv =mt, wheres andt are the integers of Bézout's identity. This may be seen by multiplying Bézout's identity bym,
mg =msa +mtb.
Therefore, the set of all numbersua +vb is equivalent to the set of multiplesm ofg. In other words, the set of all possible sums of integer multiples of two numbers (a andb) is equivalent to the set of multiples ofgcd(a,b). The GCD is said to be the generator of theideal ofa andb. This GCD definition led to the modernabstract algebraic concepts of aprincipal ideal (an ideal generated by a single element) and aprincipal ideal domain (adomain in which every ideal is a principal ideal).
Certain problems can be solved using this result.[60] For example, consider two measuring cups of volumea andb. By adding/subtractingu multiples of the first cup andv multiples of the second cup, any volumeua +vb can be measured out. These volumes are all multiples ofg = gcd(a,b).
The integerss andt of Bézout's identity can be computed efficiently using theextended Euclidean algorithm. This extension adds two recursive equations to Euclid's algorithm[61]
sk =sk−2 −qksk−1
tk =tk−2 −qktk−1
with the starting values
s−2 = 1,t−2 = 0
s−1 = 0,t−1 = 1.
Using this recursion, Bézout's integerss andt are given bys =sN andt =tN, whereN + 1 is the step on which the algorithm terminates withrN+1 = 0.
The validity of this approach can be shown by induction. Assume that the recursion formula is correct up to stepk − 1 of the algorithm; in other words, assume that
rj =sja +tjb
for allj less thank. Thekth step of the algorithm gives the equation
rk =rk−2 −qkrk−1.
Since the recursion formula has been assumed to be correct forrk−2 andrk−1, they may be expressed in terms of the correspondings andt variables
rk = (sk−2a +tk−2b) −qk(sk−1a +tk−1b).
Rearranging this equation yields the recursion formula for stepk, as required
The integerss andt can also be found using an equivalentmatrix method.[62] The sequence of equations of Euclid's algorithm
can be written as a product of2×2 quotient matrices multiplying a two-dimensional remainder vector
LetM represent the product of all the quotient matrices
This simplifies the Euclidean algorithm to the form
To expressg as a linear sum ofa andb, both sides of this equation can be multiplied by theinverse of the matrixM.[62][63] Thedeterminant ofM equals(−1)N+1, since it equals the product of the determinants of the quotient matrices, each of which is negative one. Since the determinant ofM is never zero, the vector of the final remainders can be solved using the inverse ofM
Since the top equation gives
g = (−1)N+1 (m22a −m12b),
the two integers of Bézout's identity ares = (−1)N+1m22 andt = (−1)Nm12. The matrix method is as efficient as the equivalent recursion, with two multiplications and two additions per step of the Euclidean algorithm.
Bézout's identity is essential to many applications of Euclid's algorithm, such as demonstrating theunique factorization of numbers into prime factors.[64] To illustrate this, suppose that a numberL can be written as a product of two factorsu andv, that is,L =uv. If another numberw also dividesL but is coprime withu, thenw must dividev, by the following argument: If the greatest common divisor ofu andw is1, then integerss andt can be found such that
1 =su +tw
by Bézout's identity. Multiplying both sides byv gives the relation:
v =suv +twv =sL +twv
Sincew divides both terms on the right-hand side, it must also divide the left-hand side,v. This result is known asEuclid's lemma.[65] Specifically, if a prime number dividesL, then it must divide at least one factor ofL. Conversely, if a numberw is coprime to each of a series of numbersa1,a2, ...,an, thenw is also coprime to their product,a1 ×a2 × ... ×an.[65]
Euclid's lemma suffices to prove that every number has a unique factorization into prime numbers.[66] To see this, assume the contrary, that there are two independent factorizations ofL intom andn prime factors, respectively
L =p1p2...pm =q1q2...qn.
Since each primep dividesL by assumption, it must also divide one of theq factors; since eachq is prime as well, it must be thatp =q. Iteratively dividing by thep factors shows that eachp has an equal counterpartq; the two prime factorizations are identical except for their order. The unique factorization of numbers into primes has many applications in mathematical proofs, as shown below.
Plot of a linearDiophantine equation,9x + 12y = 483. The solutions are shown as blue circles.
Diophantine equations are equations in which the solutions are restricted to integers; they are named after the 3rd-century Alexandrian mathematicianDiophantus.[67] A typicallinear Diophantine equation seeks integersx andy such that[68]
ax +by =c
wherea,b andc are given integers. This can be written as an equation forx inmodular arithmetic:
ax ≡c modb.
Letg be the greatest common divisor ofa andb. Both terms inax +by are divisible byg; therefore,c must also be divisible byg, or the equation has no solutions. By dividing both sides byc/g, the equation can be reduced to Bezout's identity
sa +tb =g,
wheres andt can be found by theextended Euclidean algorithm.[69] This provides one solution to the Diophantine equation,x1 =s (c/g) andy1 =t (c/g).
In general, a linear Diophantine equation has no solutions, or an infinite number of solutions.[70] To find the latter, consider two solutions,(x1,y1) and(x2,y2), where
ax1 +by1 =c =ax2 +by2
or equivalently
a(x1 −x2) =b(y2 −y1).
Therefore, the smallest difference between twox solutions isb/g, whereas the smallest difference between twoy solutions isa/g. Thus, the solutions may be expressed as
x =x1 −bu/g
y =y1 +au/g.
By allowingu to vary over all possible integers, an infinite family of solutions can be generated from a single solution(x1,y1). If the solutions are required to bepositive integers(x > 0,y > 0), only a finite number of solutions may be possible. This restriction on the acceptable solutions allows some systems of Diophantine equations with more unknowns than equations to have a finite number of solutions;[71] this is impossible for asystem of linear equations when the solutions can be anyreal number (seeUnderdetermined system).
Afinite field is a set of numbers with four generalized operations. The operations are called addition, subtraction, multiplication and division and have their usual properties, such ascommutativity,associativity anddistributivity. An example of a finite field is the set of 13 numbers{0, 1, 2, ..., 12} usingmodular arithmetic. In this field, the results of any mathematical operation (addition, subtraction, multiplication, or division) is reducedmodulo13; that is, multiples of13 are added or subtracted until the result is brought within the range0–12. For example, the result of5 × 7 = 35 mod 13 = 9. Such finite fields can be defined for any primep; using more sophisticated definitions, they can also be defined for any powerm of a primepm. Finite fields are often calledGalois fields, and are abbreviated asGF(p) orGF(pm).
In such a field withm numbers, every nonzero elementa has a uniquemodular multiplicative inverse,a−1 such thataa−1 =a−1a ≡ 1 modm. This inverse can be found by solving the congruence equationax ≡ 1 modm,[72] or the equivalent linear Diophantine equation[73]
ax +my = 1.
This equation can be solved by the Euclidean algorithm, as describedabove. Finding multiplicative inverses is an essential step in theRSA algorithm, which is widely used inelectronic commerce; specifically, the equation determines the integer used to decrypt the message.[74] Although the RSA algorithm usesrings rather than fields, the Euclidean algorithm can still be used to find a multiplicative inverse where one exists. The Euclidean algorithm also has other applications inerror-correcting codes; for example, it can be used as an alternative to theBerlekamp–Massey algorithm for decodingBCH andReed–Solomon codes, which are based on Galois fields.[75]
Euclid's algorithm can also be used to solve multiple linear Diophantine equations.[76] Such equations arise in theChinese remainder theorem, which describes a novel method to represent an integerx. Instead of representing an integer by its digits, it may be represented by its remaindersxi modulo a set ofN coprime numbersmi:[77]
The goal is to determinex from itsN remaindersxi. The solution is to combine the multiple equations into a single linear Diophantine equation with a much larger modulusM that is the product of all the individual modulimi, and defineMi as
Thus, eachMi is the product of all the moduliexceptmi. The solution depends on findingN new numbershi such that
With these numbershi, any integerx can be reconstructed from its remaindersxi by the equation
Since these numbershi are the multiplicative inverses of theMi, they may be found using Euclid's algorithm as described in the previous subsection.
The Euclidean algorithm can be used to arrange the set of all positiverational numbers into an infinitebinary search tree, called theStern–Brocot tree.The number 1 (expressed as a fraction 1/1) is placed at the root of the tree, and the location of any other numbera/b can be found by computing gcd(a,b) using the original form of the Euclidean algorithm, in which each step replaces the larger of the two given numbers by its difference with the smaller number (not its remainder), stopping when two equal numbers are reached. A step of the Euclidean algorithm that replaces the first of the two numbers corresponds to a step in the tree from a node to its right child, and a step that replaces the second of the two numbers corresponds to a step in the tree from a node to its left child. The sequence of steps constructed in this way does not depend on whethera/b is given in lowest terms, and forms a path from the root to a node containing the numbera/b.[78] This fact can be used to prove that each positive rational number appears exactly once in this tree.
For example, 3/4 can be found by starting at the root, going to the left once, then to the right twice:
The Stern–Brocot tree, and the Stern–Brocot sequences of orderi fori = 1, 2, 3, 4
The Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called theCalkin–Wilf tree. The difference is that the path is reversed: instead of producing a path from the root of the tree to a target, it produces a path from the target to the root.
The Euclidean algorithm has a close relationship withcontinued fractions.[79] The sequence of equations can be written in the form
The last term on the right-hand side always equals the inverse of the left-hand side of the next equation. Thus, the first two equations may be combined to form
The third equation may be used to substitute the denominator termr1/r0, yielding
The final ratio of remaindersrk/rk−1 can always be replaced using the next equation in the series, up to the final equation. The result is a continued fraction
In the worked exampleabove, the gcd(1071, 462) was calculated, and the quotientsqk were 2, 3 and 7, respectively. Therefore, the fraction 1071/462 may be written
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 liney =Φx, whereΦ is thegolden ratio.
The computational efficiency of Euclid's algorithm has been studied thoroughly.[86] This efficiency can be described by the number of division steps the algorithm requires, multiplied by the computational expense of each step. The first known analysis of Euclid's algorithm is due toA. A. L. Reynaud in 1811,[87] who showed that the number of division steps on input (u,v) is bounded byv; later he improved this tov/2 + 2. Later, in 1841,P. J. E. Finck showed[88] that the number of division steps is at most 2 log2v + 1, and hence Euclid's algorithm runs in time polynomial in the size of the input.[89]Émile Léger, in 1837, studied the worst case, which is when the inputs are consecutiveFibonacci numbers.[89] Finck's analysis was refined byGabriel Lamé in 1844,[90] who showed that the number of steps required for completion is never more than five times the numberh of base-10 digits of the smaller number b.[91][92]
In theuniform cost model (suitable for analyzing the complexity of gcd calculation on numbers that fit into a single machine word), each step of the algorithm takesconstant time, and Lamé's analysis implies that the total running time is alsoO(h). However, in a model of computation suitable for computation with larger numbers, the computational expense of a single remainder computation in the algorithm can be as large asO(h2).[93] In this case the total time for all of the steps of the algorithm can be analyzed using atelescoping series, showing that it is alsoO(h2). Modern algorithmic techniques based on theSchönhage–Strassen algorithm for fast integer multiplication can be used to speed this up, leading toquasilinear algorithms for the GCD.[94][95]
The number of steps to calculate the GCD of two natural numbers,a andb, may be denoted byT(a, b).[96] Ifg is the GCD ofa andb, thena = mg andb = ng for two coprime numbersm andn. Then
T(a,b) =T(m,n)
as may be seen by dividing all the steps in the Euclidean algorithm byg.[97] By the same argument, the number of steps remains the same ifa andb are multiplied by a common factorw:T(a,b) =T(wa,wb). Therefore, the number of stepsT may vary dramatically between neighboring pairs of numbers, such as T(a,b) and T(a, b + 1), depending on the size of the two GCDs.
The recursive nature of the Euclidean algorithm gives another equation
If the Euclidean algorithm requiresN steps for a pair of natural numbersa > b > 0, the smallest values ofa andb for which this is true are theFibonacci numbersFN+2 andFN+1, respectively.[98] More precisely, if the Euclidean algorithm requiresN steps for the paira > b, then one hasa ≥ FN+2 andb ≥ FN+1. This can be shown byinduction.[99] IfN = 1,b dividesa with no remainder; the smallest natural numbers for which this is true isb = 1 anda = 2, which areF2 andF3, respectively. Now assume that the result holds for all values ofN up toM − 1. The first step of theM-step algorithm isa = q0b + r0, and the Euclidean algorithm requiresM − 1 steps for the pairb > r0. By induction hypothesis, one hasb ≥ FM+1 andr0 ≥ FM. Therefore,a = q0b + r0 ≥ b + r0 ≥ FM+1 + FM = FM+2,which is the desired inequality.This proof, published byGabriel Lamé in 1844, represents the beginning ofcomputational complexity theory,[100] and also the first practical application of the Fibonacci numbers.[98]
This result suffices to show that the number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10).[101] For if the algorithm requiresN steps, thenb is greater than or equal toFN+1 which in turn is greater than or equal toφN−1, whereφ is thegolden ratio. Sinceb ≥ φN−1, thenN − 1 ≤ logφb. Since log10φ > 1/5, (N − 1)/5 < log10φ logφb = log10b. Thus,N ≤ 5 log10b. Thus, the Euclidean algorithm always needs less thanO(h) divisions, whereh is the number of digits in the smaller numberb.
The average number of steps taken by the Euclidean algorithm has been defined in three different ways. The first definition is the average timeT(a) required to calculate the GCD of a given numbera and a smaller natural numberb chosen with equal probability from the integers 0 toa − 1[96]
However, sinceT(a, b) fluctuates dramatically with the GCD of the two numbers, the averaged functionT(a) is likewise "noisy".[102]
To reduce this noise, a second averageτ(a) is taken over all numbers coprime witha
In each stepk of the Euclidean algorithm, the quotientqk and remainderrk are computed for a given pair of integersrk−2 andrk−1
rk−2 =qkrk−1 +rk.
The computational expense per step is associated chiefly with findingqk, since the remainderrk can be calculated quickly fromrk−2,rk−1, andqk
rk =rk−2 −qkrk−1.
The computational expense of dividingh-bit numbers scales asO(h(ℓ + 1)), whereℓ is the length of the quotient.[93]
For comparison, Euclid's original subtraction-based algorithm can be much slower. A single integer division is equivalent to the quotientq number of subtractions. If the ratio ofa andb is very large, the quotient is large and many subtractions will be required. On the other hand, it has been shown that the quotients are very likely to be small integers. The probability of a given quotientq is approximatelyln |u/(u − 1)| whereu = (q + 1)2.[114] For illustration, the probability of a quotient of 1, 2, 3, or 4 is roughly 41.5%, 17.0%, 9.3%, and 5.9%, respectively. Since the operation of subtraction is faster than division, particularly for large numbers,[115] the subtraction-based Euclid's algorithm is competitive with the division-based version.[116] This is exploited in thebinary version of Euclid's algorithm.[117]
Combining the estimated number of steps with the estimated computational expense per step shows that the Euclid's algorithm grows quadratically (h2) with the average number of digitsh in the initial two numbersa andb. Leth0,h1, ...,hN−1 represent the number of digits in the successive remaindersr0,r1, ...,rN−1. Since the number of stepsN grows linearly withh, the running time is bounded by
Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity.[118] For comparison, the efficiency of alternatives to Euclid's algorithm may be determined.
One inefficient approach to finding the GCD of two natural numbersa andb is to calculate all their common divisors; the GCD is then the largest common divisor. The common divisors can be found by dividing both numbers by successive integers from 2 to the smaller numberb. The number of steps of this approach grows linearly withb, or exponentially in the number of digits. Another inefficient approach is to find the prime factors of one or both numbers. As notedabove, the GCD equals the product of the prime factors shared by the two numbersa andb.[8] Present methods forprime factorization are also inefficient; many modern cryptography systems even rely on that inefficiency.[11]
Thebinary GCD algorithm is an efficient alternative that substitutes division with faster operations by exploiting thebinary representation used by computers.[119][120] However, this alternative also scales likeO(h²). It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way.[94] Additional efficiency can be gleaned by examining only the leading digits of the two numbersa andb.[121][122] The binary algorithm can be extended to other bases (k-ary algorithms),[123] with up to fivefold increases in speed.[124]Lehmer's GCD algorithm uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases.
A recursive approach for very large integers (with more than 25,000 digits) leads toquasilinear integer GCD algorithms,[125] such as those of Schönhage,[126][127] and Stehlé and Zimmermann.[128] These algorithms exploit the 2×2 matrix form of the Euclidean algorithm givenabove. These quasilinear methods generally scale asO(h logh2 log logh).[94][95]
Although the Euclidean algorithm is used to find the greatest common divisor of two natural numbers (positive integers), it may be generalized to the real numbers, and to other mathematical objects, such aspolynomials,[129]quadratic integers[130] andHurwitz quaternions.[131] In the latter cases, the Euclidean algorithm is used to demonstrate the crucial property of unique factorization, i.e., that such numbers can be factored uniquely intoirreducible elements, the counterparts of prime numbers. Unique factorization is essential to many proofs of number theory.
Euclid's algorithm can be applied toreal numbers, as described by Euclid in Book 10 of hisElements. The goal of the algorithm is to identify a real numberg such that two given real numbers,a andb, are integer multiples of it:a =mg andb =ng, wherem andn areintegers.[28] This identification is equivalent to finding aninteger relation among the real numbersa andb; that is, it determines integerss andt such thatsa +tb = 0. If such an equation is possible,a andb are called commensurable lengths, otherwise they areincommensurable lengths.[132][133]
The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remaindersrk are real numbers, although the quotientsqk are integers as before. Second, the algorithm is not guaranteed to end in a finite numberN of steps. If it does, the fractiona/b is a rational number, i.e., the ratio of two integers
and can be written as a finite continued fraction[q0;q1,q2, ...,qN]. If the algorithm does not stop, the fractiona/b is anirrational number and can be described by an infinite continued fraction[q0;q1,q2, …].[134] Examples of infinite continued fractions are thegolden ratioφ = [1; 1, 1, ...] and thesquare root of two,√2 = [1; 2, 2, ...].[135] When applied to two arbitrary real numbers, the algorithm is unlikely to stop, sincealmost all ratiosa/b of two real numbers are irrational.[136]
An infinite continued fraction may be truncated at a stepk [q0;q1,q2, ...,qk] to yield an approximation toa/b that improves ask is increased. The approximation is described byconvergentsmk/nk; the numerator and denominators are coprime and obey therecurrence relation
wherem−1 =n−2 = 1 andm−2 =n−1 = 0 are the initial values of the recursion. The convergentmk/nk is the bestrational number approximation toa/b with denominatornk:[137]
Polynomials in a single variablex can be added, multiplied and factored intoirreducible polynomials, which are the analogs of the prime numbers for integers. The greatest common divisor polynomialg(x) of two polynomialsa(x) andb(x) is defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm.[129] The basic procedure is similar to that for integers. At each stepk, a quotient polynomialqk(x) and a remainder polynomialrk(x) are identified to satisfy the recursive equation
wherer−2(x) =a(x) andr−1(x) =b(x). 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:deg[rk(x)] < deg[rk−1(x)]. Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps. The last nonzero remainder is the greatest common divisor of the original two polynomials,a(x) andb(x).[138]
For example, consider the following two quartic polynomials, which each factor into two quadratic polynomials
Dividinga(x) byb(x) yields a remainderr0(x) =x3 + (2/3)x2 + (5/3)x − (2/3). In the next step,b(x) is divided byr0(x) yielding a remainderr1(x) =x2 +x + 2. Finally, dividingr0(x) byr1(x) yields a zero remainder, indicating thatr1(x) is the greatest common divisor polynomial ofa(x) andb(x), consistent with their factorization.
Many of the applications described above for integers carry over to polynomials.[139] The Euclidean algorithm can be used to solve linear Diophantine equations and Chinese remainder problems for polynomials; continued fractions of polynomials can also be defined.
Finally, the coefficients of the polynomials need not be drawn from integers, real numbers or even the complex numbers. For example, the coefficients may be drawn from a general field, such as the finite fieldsGF(p) described above. The corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.[129]
The Euclidean algorithm developed for two Gaussian integersα andβ is nearly the same as that for ordinary integers,[143] but differs in two respects. As before, we setr−2 =α andr−1 =β, and the task at each stepk is to identify a quotientqk and a remainderrk such that
where every remainder is strictly smaller than its predecessor:|rk| < |rk−1|. The first difference is that the quotients and remainders are themselves Gaussian integers, and thus arecomplex numbers. The quotientsqk are generally found by rounding the real and complex parts of the exact ratio (such as the complex numberα/β) to the nearest integers.[143] The second difference lies in the necessity of defining how one complex remainder can be "smaller" than another. To do this, anorm functionf(u +vi) =u2 +v2 is defined, which converts every Gaussian integeru +vi into an ordinary integer. After each stepk of the Euclidean algorithm, the norm of the remainderf(rk) is smaller than the norm of the preceding remainder,f(rk−1). Since the norm is a nonnegative integer and decreases with every step, the Euclidean algorithm for Gaussian integers ends in a finite number of steps.[144] The final nonzero remainder isgcd(α,β), the Gaussian integer of largest norm that divides bothα andβ; it is unique up to multiplication by a unit,±1 or±i.[145]
Many of the other applications of the Euclidean algorithm carry over to Gaussian integers. For example, it can be used to solve linear Diophantine equations and Chinese remainder problems for Gaussian integers;[146] continued fractions of Gaussian integers can also be defined.[143]
A set of elements under twobinary operations, denoted as addition and multiplication, is called aEuclidean domain if it forms acommutative ringR and, roughly speaking, if a generalized Euclidean algorithm can be performed on them.[147][148] The two operations of such a ring need not be the addition and multiplication of ordinary arithmetic; rather, they can be more general, such as the operations of amathematical group ormonoid. Nevertheless, these general operations should respect many of the laws governing ordinary arithmetic, such ascommutativity,associativity anddistributivity.
The generalized Euclidean algorithm requires aEuclidean function, i.e., a mappingf fromR into the set of nonnegative integers such that, for any two nonzero elementsa andb inR, there existq andr inR such thata =qb +r andf(r) <f(b).[149] Examples of such mappings are the absolute value for integers, the degree forunivariate polynomials, and the norm for Gaussian integersabove.[150][151] The basic principle is that each step of the algorithm reducesf inexorably; hence, iff can be reduced only a finite number of times, the algorithm must stop in a finite number of steps. This principle relies on thewell-ordering property of the non-negative integers, which asserts that every non-empty set of non-negative integers has a smallest member.[152]
Thefundamental theorem of arithmetic applies to any Euclidean domain: Any number from a Euclidean domain can be factored uniquely intoirreducible elements. Any Euclidean domain is aunique factorization domain (UFD), although the converse is not true.[152] The Euclidean domains and the UFD's are subclasses of theGCD domains, domains in which a greatest common divisor of two numbers always exists.[153] In other words, a greatest common divisor may exist (for all pairs of elements in a domain), although it may not be possible to find it using a Euclidean algorithm. A Euclidean domain is always aprincipal ideal domain (PID), anintegral domain in which everyideal is aprincipal ideal.[154] Again, the converse is not true: not every PID is a Euclidean domain.
The unique factorization of Euclidean domains is useful in many applications. For example, the unique factorization of the Gaussian integers is convenient in deriving formulae for allPythagorean triples and in provingFermat's theorem on sums of two squares.[142] Unique factorization was also a key element in an attempted proof ofFermat's Last Theorem published in 1847 by Gabriel Lamé, the same mathematician who analyzed the efficiency of Euclid's algorithm, based on a suggestion ofJoseph Liouville.[155] Lamé's approach required the unique factorization of numbers of the formx +ωy, wherex andy are integers, andω =e2iπ/n is annth root of 1, that is,ωn = 1. Although this approach succeeds for some values ofn (such asn = 3, theEisenstein integers), in general such numbers donot factor uniquely. This failure of unique factorization in somecyclotomic fields ledErnst Kummer to the concept ofideal numbers and, later,Richard Dedekind toideals.[156]
Distribution of Eisenstein primesu +vω in the complex plane, with norms less than 500. The numberω is acube root of 1.
Thequadratic integer rings are helpful to illustrate Euclidean domains. Quadratic integers are generalizations of the Gaussian integers in which theimaginary uniti is replaced by a numberω. Thus, they have the formu +vω, whereu andv are integers andω has one of two forms, depending on a parameterD. IfD does not equal a multiple of four plus one, then
If, however,D does equal a multiple of four plus one, then
If the functionf corresponds to anorm function, such as that used to order the Gaussian integersabove, then the domain is known asnorm-Euclidean. The norm-Euclidean rings of quadratic integers are exactly those whereD 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.[157][158] The casesD = −1 andD = −3 yield theGaussian integers andEisenstein integers, respectively.
Iff is allowed to be any Euclidean function, then the list of possible values ofD for which the domain is Euclidean is not yet known.[159] The first example of a Euclidean domain that was not norm-Euclidean (withD = 69) was published in 1994.[159] In 1973, Weinberger proved that a quadratic integer ring withD > 0 is Euclidean if, and only if, it is aprincipal ideal domain, provided that thegeneralized Riemann hypothesis holds.[130]
The Euclidean algorithm may be applied to some noncommutative rings such as the set ofHurwitz quaternions.[131][160] Letα andβ represent two elements from such a ring. They have a common right divisorδ ifα =ξδ andβ =ηδ for some choice ofξ andη in the ring. Similarly, they have a common left divisor ifα =dξ andβ =dη for some choice ofξ andη in the ring. Since multiplication is not commutative, there are two versions of the Euclidean algorithm, one for right divisors and one for left divisors.[131][160] Choosing the right divisors, the first step in finding thegcd(α,β) by the Euclidean algorithm can be written
whereψ0 represents the quotient andρ0 the remainder. Here the quotient and remainder are chosen so that (if nonzero) the remainder hasN(ρ0) <N(β) for a "Euclidean function"N defined analogously to the Euclidean functions ofEuclidean domains in the non-commutative case.[160] This equation shows that any common right divisor ofα andβ is likewise a common divisor of the remainderρ0. The analogous equation for the left divisors would be
With either choice, the process is repeated as above until the greatest common right or left divisor is identified. As in the Euclidean domain, the "size" of the remainderρ0 (formally, its Euclidean function or "norm") must be strictly smaller thanβ, and there must be only a finite number of possible sizes forρ0, so that the algorithm is guaranteed to terminate.[161]
Many results for the GCD carry over to noncommutative numbers. For example,Bézout's identity states that the rightgcd(α,β) can be expressed as a linear combination ofα andβ.[162] In other words, there are numbersσ andτ such that
The analogous identity for the left GCD is nearly the same:
Bézout's identity can be used to solve Diophantine equations. For instance, one of the standard proofs ofLagrange'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.[161]
^Lamé, Gabriel (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers".Comptes Rendus des Séances de l'Académie des Sciences (in French).19:867–870.
^Jones, A. (1994). "Greek mathematics to AD 300".Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. pp. 46–48.ISBN0-415-09238-8.
^von Fritz, K. (1945). "The Discovery of Incommensurability by Hippasus of Metapontum".Annals of Mathematics.46 (2):242–264.doi:10.2307/1969021.JSTOR1969021.
^Fowler, D. H. (1987).The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. pp. 31–66.ISBN0-19-853912-6.
^Becker, O. (1933). "Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid".Quellen und Studien zur Geschichte der Mathematik B.2:311–333.
^Cole, A. J.; Davie, A. J. T. (1969). "A game based on the Euclidean algorithm and a winning strategy for it".Math. Gaz.53 (386):354–357.doi:10.2307/3612461.JSTOR3612461.S2CID125164797.
^Spitznagel, E. L. (1973). "Properties of a game based on Euclid's algorithm".Math. Mag.46 (2):87–92.doi:10.2307/2689037.JSTOR2689037.
^Lamé, G. (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers".Comptes Rendus de l'Académie des Sciences (in French).19:867–870.
^Grossman, H. (1924). "On the Number of Divisions in Finding a G.C.D".The American Mathematical Monthly.31 (9): 443.doi:10.2307/2298146.JSTOR2298146.
^Heilbronn, H. A. (1969). "On the Average Length of a Class of Finite Continued Fractions". In Paul Turán (ed.).Number Theory and Analysis. New York: Plenum. pp. 87–96.LCCN76016027.
^Sorenson, Jonathan P. (2004). "An analysis of the generalized binary GCD algorithm".High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams. Fields Institute Communications. Vol. 41. Providence, RI: American Mathematical Society. pp. 327–340.ISBN9780821887592.MR2076257.The algorithms that are used the most in practice today [for computing greatest common divisors] are probably the binary algorithm and Euclid's algorithm for smaller numbers, and either Lehmer's algorithm or Lebealean's version of thek-ary GCD algorithm for larger numbers.
^Cesari, G. (1998). "Parallel implementation of Schönhage's integer GCD algorithm". In G. Buhler (ed.).Algorithmic Number Theory: Proc. ANTS-III, Portland, OR. Lecture Notes in Computer Science. Vol. 1423. New York: Springer-Verlag. pp. 64–76.
^Stehlé, D.; Zimmermann, P. (2005). "Gal's accurate tables method revisited".Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17). Los Alamitos, CA:IEEE Computer Society Press.
^abWeinberger, P. (1973). "On Euclidean rings of algebraic integers".Proc. Sympos. Pure Math. Proceedings of Symposia in Pure Mathematics.24. Providence, Rhode Island:321–332.doi:10.1090/pspum/024/0337902.ISBN9780821814246.
^Adams, William W.; Goldstein, Larry Joel (1976).Introduction to Number Theory. Prentice-Hall. Exercise 24, p. 205.ISBN9780134912820.State and prove an analogue of the Chinese remainder theorem for the Gaussian integers.
^abcBueso, Gómez-Torrecillas & Verschoren (2003); see pp. 37-38 for non-commutative extensions of the Euclidean algorithm and Corollary 4.35, p. 40, for more examples of noncommutative rings to which they apply.
