Euclidean algorithm

Template:Short description Template:About Template:Distinguish Template:Featured article

File:Euclid's algorithm Book VII Proposition 2 3.svg

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).

In mathematics, the Euclidean algorithm,<ref group=note>Some widely used textbooks, such as I. N. Herstein's Topics in Algebra and Serge Lang's Algebra, use the term "Euclidean algorithm" to refer to Euclidean division</ref> or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (Template:Circa). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

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, Template:Math is the GCD of Template:Math and Template:Math (as Template:Math and Template:Math, and the same number Template:Math is also the GCD of Template:Math and Template:Math. 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. By reversing the steps or using the extended Euclidean algorithm, the GCD can be expressed as a linear combination of the two original numbers, that is the sum of the two numbers, each multiplied by an integer (for example, Template:Math). The fact that the GCD can always be expressed in this way is known as Bé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 by Gabriel Lamé in 1844 (Lamé's Theorem),<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref> and marks the beginning of computational complexity theory. Additional methods for improving the algorithm's efficiency were developed in the 20th century.

The Euclidean algorithm has many theoretical and practical applications. It is used for reducing fractions to their simplest form and for performing division in modular arithmetic. Computations using this algorithm form part of the cryptographic protocols that are used to secure internet communications, and in methods for breaking these cryptosystems by factoring large composite numbers. The Euclidean algorithm may be used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem, to construct continued fractions, and to find accurate rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in number theory such as Lagrange's four-square theorem and the uniqueness of prime factorizations.

The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. This led to modern abstract algebraic notions such as Euclidean domains.

Background: greatest common divisorEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers Template:Mvar and Template:Mvar. The greatest common divisor Template:Mvar is the largest natural number that divides both Template:Mvar and Template:Mvar without leaving a remainder. Synonyms for GCD include greatest common factor (GCF), highest common factor (HCF), highest common divisor (HCD), and greatest common measure (GCM). The greatest common divisor is often written as Template:Math or, more simply, as Template:Math,<ref>Template:Harvnb</ref> although the latter notation is ambiguous, also used for concepts such as an ideal in the ring of integers, which is closely related to GCD.

If Template:Math, then Template:Mvar and Template:Mvar are said to be coprime (or relatively prime).<ref>Template:Harvnb</ref> This property does not imply that Template:Mvar or Template:Mvar are themselves prime numbers.<ref>Template:Harvnb</ref> For example, Template:Math and Template:Math factor as Template:Math and Template:Math, so they are not prime, but their prime factors are different, so Template:Math and Template:Math are coprime, with no common factors other than Template:Math.

File:24x60.svg

A 24×60 rectangle is covered with ten 12×12 square tiles, where 12 is the GCD of 24 and 60. More generally, an Template:Math rectangle can be covered with square tiles of side-length Template:Mvar only if Template:Mvar is a common divisor of Template:Math and Template:Math.

Let Template:Math. Since Template:Mvar and Template:Mvar are both multiples of Template:Mvar, they can be written Template:Math and Template:Mvar, and there is no larger number Template:Math for which this is true. The natural numbers Template:Mvar and Template:Mvar must be coprime, since any common factor could be factored out of Template:Mvar and Template:Mvar to make Template:Mvar greater. Thus, any other number Template:Mvar that divides both Template:Mvar and Template:Mvar must also divide Template:Mvar. The greatest common divisor Template:Mvar of Template:Mvar and Template:Mvar is the unique (positive) common divisor of Template:Mvar and Template:Mvar that is divisible by any other common divisor Template:Mvar.<ref>Template:Harvnb</ref>

The greatest common divisor can be visualized as follows.<ref>Template:Cite book</ref> Consider a rectangular area Template:Mvar by Template:Mvar, and any common divisor Template:Mvar that divides both Template:Mvar and Template:Mvar exactly. The sides of the rectangle can be divided into segments of length Template:Mvar, which divides the rectangle into a grid of squares of side length Template:Mvar. The GCD Template:Mvar is the largest value of Template:Mvar for which this is possible. For illustration, a Template:Math rectangular area can be divided into a grid of: Template:Math squares, Template:Math squares, Template:Math squares, Template:Math squares, Template:Math squares or Template:Math squares. Therefore, Template:Math is the GCD of Template:Math and Template:Math. A Template:Math rectangular area can be divided into a grid of Template:Math squares, with two squares along one edge (Template:Math) and five squares along the other (Template:Math).

The greatest common divisor of two numbers Template:Mvar and Template:Mvar 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 Template:Mvar and Template:Mvar.<ref name="Schroeder_21" >Template:Harvnb</ref> For example, since Template:Math can be factored into Template:Math, and Template:Math can be factored into Template:Math, the GCD of Template:Math and Template:Math equals Template:Math, the product of their shared prime factors (with 3 repeated since Template:Math divides both). If two numbers have no common prime factors, their GCD is Template:Math (obtained here as an instance of the empty product); in other words, they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors.<ref>Template:Harvnb</ref><ref>Template:Cite book</ref> Factorization of large integers is believed to be a computationally very difficult problem, and the security of many widely used cryptographic protocols is based upon its infeasibility.<ref name="Schroeder_216" >Template:Harvnb</ref>

Another definition of the GCD is helpful in advanced mathematics, particularly ring theory.<ref name="Leveque_p33" /> The greatest common divisor Template:Mvar of two nonzero numbers Template:Mvar and Template:Mvar is also their smallest positive integral linear combination, that is, the smallest positive number of the form Template:Math where Template:Mvar and Template:Mvar are integers. The set of all integral linear combinations of Template:Mvar and Template:Mvar is actually the same as the set of all multiples of Template:Mvar (Template:Mvar, where Template:Mvar is an integer). In modern mathematical language, the ideal generated by Template:Mvar and Template:Mvar is the ideal generated by Template:Mvar alone (an ideal generated by a single element is called a principal 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 of Template:Mvar and Template:Mvar also divides the GCD (it divides both terms of Template:Math). 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,<ref>Template:Harvnb</ref> but it can also be calculated by repeatedly taking the GCDs of pairs of numbers.<ref>Template:Harvnb</ref> For example,

Template:Math

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

ProcedureEdit

Template:Euclidean algorithm steps The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers <math>r_{-2} = a</math> and <math>r_{-1} = b</math> and will eventually terminate with the integer zero: <math>\{ r_{-2} = a,\ r_{-1} = b,\ r_0,\ r_1,\ \cdots,\ r_{n-1},\ r_n = 0 \}</math> with <math>r_{k+1} < r_k</math>. The integer <math>r_{n-1}</math> will then be the GCD and we can state <math>\text{gcd}(a,b) = r_{n-1}</math>. The algorithm indicates how to construct the intermediate remainders <math>r_k</math> via division-with-remainder on the preceding pair <math>(r_{k-2},\ r_{k-1})</math> by finding an integer quotient <math>q_k</math> so that:

Because the sequence of non-negative integers <math>\{ r_k \}</math> is strictly decreasing, it eventually must terminate. In other words, since <math>r_k \ge 0</math> for every <math>k</math>, and each <math>r_k</math> is an integer that is strictly smaller than the preceding <math>r_{k-1}</math>, there eventually cannot be a non-negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the Template:Mathth step with <math>r_n</math> equal to zero.<ref>Template:Harvnb</ref>

To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially <math>\{r_{-2} = 1071,\ r_{-1} = 462 \}</math> and in order to find <math>r_0</math>, we need to find integers <math>q_0</math> and <math>r_0 < r_{-1}</math> such that:

<math>1071 = q_0 \cdot 462 + r_0</math>.

This is the quotient <math>q_0 = 2</math> since <math>1071 = 2 \cdot 462 + 147</math>. This determines <math>r_0 = 147</math> and so the sequence is now <math>\{1071,\ 462,\ r_0 = 147 \}</math>. The next step is to continue the sequence to find <math>r_1</math> by finding integers <math>q_1</math> and <math>r_1 < r_0</math> such that:

<math>462 = q_1 \cdot 147 + r_1</math>.

This is the quotient <math>q_1 = 3</math> since <math>462 = 3 \cdot 147 + 21</math>. This determines <math>r_1 = 21</math> and so the sequence is now <math>\{1071,\ 462,\ 147,\ r_1 = 21 \}</math>. The next step is to continue the sequence to find <math>r_2</math> by finding integers <math>q_2</math> and <math>r_2 < r_1</math> such that:

<math>147 = q_2 \cdot 21 + r_2</math>.

This is the quotient <math>q_2 = 7</math> since <math>147 = 7 \cdot 21 + 0</math>. This determines <math>r_2 = 0</math> and so the sequence is completed as <math>\{1071,\ 462,\ 147,\ 21,\ r_2 = 0 \}</math> as no further non-negative integer smaller than <math>0</math> can be found. The penultimate remainder <math>21</math> is therefore the requested GCD:

We can generalize slightly by dropping any ordering requirement on the initial two values <math>a</math> and <math>b</math>. If <math>a = b</math>, the algorithm may continue and trivially find that <math>\text{gcd}(a,\ a) = a</math> as the sequence of remainders will be <math>\{a,\ a,\ 0\}</math>. If <math>a < b</math>, then we can also continue since <math>a \equiv 0 \cdot b + a</math>, suggesting the next remainder should be <math>a</math> itself, and the sequence is <math>\{a,\ b,\ a,\ \cdots \}</math>. Normally, this would be invalid because it breaks the requirement <math>r_0 < r_{-1}</math> but now we have <math>a < b</math> 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 <math>r_0 < b</math> and everything continues as above. The only modifications that need to be made are that <math>r_{k} < r_{k-1}</math> only for <math>k \ge 0</math>, and that the sub-sequence of non-negative integers <math>\{ r_{k-1} \}</math> for <math>k \ge 0</math> is strictly decreasing, therefore excluding <math>a = r_{-2}</math> from both statements.

Proof of validityEdit

The validity of the Euclidean algorithm can be proven by a two-step argument.<ref>Template:Harvnb</ref> In the first step, the final nonzero remainder Template:Math is shown to divide both Template:Math and Template:Math. Since it is a common divisor, it must be less than or equal to the greatest common divisor Template:Math. In the second step, it is shown that any common divisor of Template:Math and Template:Math, including Template:Math, must divide Template:Math; therefore, Template:Math must be less than or equal to Template:Math. These two opposite inequalities imply Template:Math.

To demonstrate that Template:Math divides both Template:Math and Template:Math (the first step), Template:Math divides its predecessor Template:Math

Template:Math

since the final remainder Template:Math is zero. Template:Math also divides its next predecessor Template:Math

Template:Math

because it divides both terms on the right-hand side of the equation. Iterating the same argument, Template:Math divides all the preceding remainders, including Template:Math and Template:Math. None of the preceding remainders Template:Math, Template:Math, etc. divide Template:Math and Template:Math, since they leave a remainder. Since Template:Math is a common divisor of Template:Math and Template:Math, Template:Math.

In the second step, any natural number Template:Math that divides both Template:Math and Template:Math (in other words, any common divisor of Template:Math and Template:Math) divides the remainders Template:Math. By definition, Template:Math and Template:Math can be written as multiples of Template:Math: Template:Math and Template:Math, where Template:Math and Template:Math are natural numbers. Therefore, Template:Math divides the initial remainder Template:Math, since Template:Math. An analogous argument shows that Template:Math also divides the subsequent remainders Template:Math, Template:Math, etc. Therefore, the greatest common divisor Template:Math must divide Template:Math, which implies that Template:Math. Since the first part of the argument showed the reverse (Template:Math), it follows that Template:Math. Thus, Template:Math is the greatest common divisor of all the succeeding pairs:<ref>Template:Harvnb</ref><ref name="Lovasz_2003">Template:Cite book</ref>

Template:Math.

Worked exampleEdit

File:Euclidean algorithm 1071 462.gif

Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions Template:Math and Template:Math. Squares of size Template:Math are placed within it leaving a Template:Math rectangle. This rectangle is tiled with Template:Math squares until a Template:Math rectangle is left, which in turn is tiled with Template:Math squares, leaving no uncovered area. The smallest square size, Template:Math, is the GCD of Template:Math and Template:Math.

For illustration, the Euclidean algorithm can be used to find the greatest common divisor of Template:Math and Template:Math. To begin, multiples of Template:Math are subtracted from Template:Math until the remainder is less than Template:Math. Two such multiples can be subtracted (Template:Math), leaving a remainder of Template:Math:

Template:Math.

Then multiples of Template:Math are subtracted from Template:Math until the remainder is less than Template:Math. Three multiples can be subtracted (Template:Math), leaving a remainder of Template:Math:

Template:Math.

Then multiples of Template:Math are subtracted from Template:Math until the remainder is less than Template:Math. Seven multiples can be subtracted (Template:Math), leaving no remainder:

Template:Math.

Since the last remainder is zero, the algorithm ends with Template:Math as the greatest common divisor of Template:Math and Template:Math. This agrees with the Template:Math found by prime factorization above. In tabular form, the steps are:

Step k	Equation	Quotient and remainder
0	Template:Math	Template:Math and Template:Math
1	Template:Math	Template:Math and Template:Math
2	Template:Math	Template:Math and Template:Math; algorithm ends

VisualizationEdit

The Euclidean algorithm can be visualized in terms of the tiling analogy given above for the greatest common divisor.<ref name="Kimberling_1983">Template:Cite journal</ref> Assume that we wish to cover an Template:Math rectangle with square tiles exactly, where Template:Math is the larger of the two numbers. We first attempt to tile the rectangle using Template:Math square tiles; however, this leaves an Template:Math residual rectangle untiled, where Template:Math. We then attempt to tile the residual rectangle with Template:Math square tiles. This leaves a second residual rectangle Template:Math, which we attempt to tile using Template:Math square tiles, and so on. The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the previous residual rectangle exactly. The length of the sides of the smallest square tile is the GCD of the dimensions of the original rectangle. For example, the smallest square tile in the adjacent figure is Template:Math (shown in red), and Template:Math is the GCD of Template:Math and Template:Math, the dimensions of the original rectangle (shown in green).

Euclidean divisionEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

At every step Template:Math, the Euclidean algorithm computes a quotient Template:Math and remainder Template:Math from two numbers Template:Math and Template:Math

Template:Math,

where the Template:Math is non-negative and is strictly less than the absolute value of Template:Math. The theorem which underlies the definition of the Euclidean division ensures that such a quotient and remainder always exist and are unique.<ref>Template:Cite book</ref>

In Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is, Template:Math is subtracted from Template:Math repeatedly until the remainder Template:Math is smaller than Template:Math. After that Template:Math and Template:Math are exchanged and the process is iterated. Euclidean division reduces all the steps between two exchanges into a single step, which is thus more efficient. Moreover, the quotients are not needed, thus one may replace Euclidean division by the modulo operation, which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply

Template:Math.

ImplementationsEdit

Implementations of the algorithm may be expressed in pseudocode. For example, the division-based version may be programmed as<ref>Template:Harvnb</ref>

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

At the beginning of the Template:Mathth iteration, the variable Template:Math holds the latest remainder Template:Math, whereas the variable Template:Math holds its predecessor, Template:Math. The step Template:Math is equivalent to the above recursion formula Template:Math. The temporary variable Template:Math holds the value of Template:Math while the next remainder Template:Math is being calculated. At the end of the loop iteration, the variable Template:Math holds the remainder Template:Math, whereas the variable Template:Math holds its predecessor, Template:Math.

(If negative inputs are allowed, or if the mod function may return negative values, the last line must be replaced with Template:Nowrap.)

In the subtraction-based version, which was Euclid's original version, the remainder calculation (Template:Nowrap) is replaced by repeated subtraction.<ref>Template:Harvnb</ref> Contrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops when Template:Math:

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

The variables Template:Math and Template:Math alternate holding the previous remainders Template:Math and Template:Math. Assume that Template:Math is larger than Template:Math at the beginning of an iteration; then Template:Math equals Template:Math, since Template:Math. During the loop iteration, Template:Math is reduced by multiples of the previous remainder Template:Math until Template:Math is smaller than Template:Math. Then Template:Math is the next remainder Template:Math. Then Template:Math is reduced by multiples of Template:Math until it is again smaller than Template:Math, giving the next remainder Template:Math, and so on.

The recursive version<ref>Template:Harvnb</ref> is based on the equality of the GCDs of successive remainders and the stopping condition Template:Math.

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

(As above, if negative inputs are allowed, or if the mod function may return negative values, the instruction Template:Nowrap must be replaced by Template:Nowrap.)

For illustration, the Template:Math is calculated from the equivalent Template:Math. The latter GCD is calculated from the Template:Math, which in turn is calculated from the Template:Math.

Method of least absolute remaindersEdit

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.<ref name="Ore_least_abs_remainders" >Template:Harvnb</ref><ref name="Stewart_1964">Template:Cite book</ref> Previously, the equation

Template:Math

assumed that Template:Math. However, an alternative negative remainder Template:Math can be computed:

Template:Math

if Template:Math or

Template:Math

if Template:Math.

If Template:Math is replaced by Template:Math. when Template:Math, then one gets a variant of Euclidean algorithm such that

Template:Math

at each step.

Leopold Kronecker has shown that this version requires the fewest steps of any version of Euclid's algorithm.<ref name="Ore_least_abs_remainders" /><ref name="Stewart_1964" /> More generally, it has been proven that, for every input numbers a and b, the number of steps is minimal if and only if Template:Math is chosen in order that <math>\left |\frac{r_{k+1}}{r_k}\right |<\frac{1}{\varphi}\sim 0.618,</math> where <math>\varphi</math> is the golden ratio.<ref>Template:Cite journal</ref>

Historical developmentEdit

File:Euklid.jpg

The Euclidean algorithm was probably invented before Euclid, depicted here holding a compass in a painting of about 1474.

The Euclidean algorithm is one of the oldest algorithms in common use.<ref name="Knuth, p. 318">Template:Harvnb, p. 318</ref> It appears in Euclid's Elements (c. 300 BC), specifically in Book 7 (Propositions 1–2) and Book 10 (Propositions 2–3). In Book 7, the algorithm is formulated for integers, whereas in Book 10, it is formulated for lengths of line segments. (In modern usage, one would say it was formulated there for real numbers. But lengths, areas, and volumes, represented as real numbers in modern usage, are not measured in the same units and there is no natural unit of length, area, or volume; the concept of real numbers was unknown at that time.) The latter algorithm is geometrical. The GCD of two lengths Template:Math and Template:Math corresponds to the greatest length Template:Math that measures Template:Math and Template:Math evenly; in other words, the lengths Template:Math and Template:Math are both integer multiples of the length Template:Math.

The algorithm was probably not discovered by Euclid, who compiled results from earlier mathematicians in his Elements.<ref name="Weil_1983">Template:Cite book</ref><ref name="Jones_1994">Template:Cite book</ref> The mathematician and historian B. L. van der Waerden suggests that Book VII derives from a textbook on number theory written by mathematicians in the school of Pythagoras.<ref name="van_der_Waerden_1954">Template:Cite book</ref> The algorithm was probably known by Eudoxus of Cnidus (about 375 BC).<ref name="Knuth, p. 318"/><ref>Template:Cite journal</ref> The algorithm may even pre-date Eudoxus,<ref>Template:Cite book</ref><ref>Template:Cite book</ref> judging from the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid and Aristotle.<ref>Template:Cite journal</ref> Claude Brezinski, following remarks by Pappus of Alexandria, credits the algorithm to Theaetetus (c. 417 – c. 369 BC).<ref>Template:Cite book</ref>

Centuries later, Euclid's algorithm was discovered independently both in India and in China,<ref name="Stillwell, p. 31">Template:Harvnb</ref> primarily to solve Diophantine equations that arose in astronomy and making accurate calendars. In the late 5th century, the Indian mathematician and astronomer Aryabhata described the algorithm as the "pulverizer",<ref name="Tattersall, p. 70">Template:Harvnb</ref> perhaps because of its effectiveness in solving Diophantine equations.<ref>Template:Harvnb</ref> Although a special case of the Chinese remainder theorem had already been described in the Chinese book Sunzi Suanjing,<ref>Template:Harvnb</ref> the general solution was published by Qin Jiushao in his 1247 book Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections).<ref>Template:Harvnb</ref> The Euclidean algorithm was first described numerically and popularized in Europe in the second edition of Bachet's Problèmes plaisants et délectables (Pleasant and enjoyable problems, 1624).<ref name="Tattersall, p. 70"/> In Europe, it was likewise used to solve Diophantine equations and in developing continued fractions. The extended Euclidean algorithm was published by the English mathematician Nicholas Saunderson,<ref>Template:Cite book</ref> who attributed it to Roger Cotes as a method for computing continued fractions efficiently.<ref>Template:Harvnb</ref>

In the 19th century, the Euclidean algorithm led to the development of new number systems, such as Gaussian integers and Eisenstein integers. In 1815, Carl Gauss used the Euclidean algorithm to demonstrate unique factorization of Gaussian integers, although his work was first published in 1832.<ref name="Gauss_1832" /> Gauss mentioned the algorithm in his Disquisitiones Arithmeticae (published 1801), but only as a method for continued fractions.<ref name="Stillwell, p. 31"/> Peter Gustav Lejeune Dirichlet seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory.<ref>Template:Harvnb</ref> 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.<ref>Template:Harvnb</ref> Lejeune Dirichlet's lectures on number theory were edited and extended by Richard Dedekind, who used Euclid's algorithm to study algebraic integers, a new general type of number. For example, Dedekind was the first to prove Fermat's two-square theorem using the unique factorization of Gaussian integers.<ref>Richard Dedekind in Template:Harvnb</ref> Dedekind also defined the concept of a Euclidean domain, a number system in which a generalized version of the Euclidean algorithm can be defined (as described below). In the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of ideals.<ref>Template:Harvnb</ref>

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

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

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

The Euclidean algorithm was the first integer relation algorithm, which is a method for finding integer relations between commensurate real numbers. Several novel integer relation algorithms have been developed, such as the algorithm of Helaman Ferguson and R.W. Forcade (1979)<ref> Template:Cite journal</ref> and the LLL algorithm.<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref>

In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called The Game of Euclid,<ref>Template:Cite journal</ref> which has an optimal strategy.<ref>Template:Cite journal</ref> The players begin with two piles of Template:Math and Template:Math stones. The players take turns removing Template:Math multiples of the smaller pile from the larger. Thus, if the two piles consist of Template:Math and Template:Math stones, where Template:Math is larger than Template:Math, the next player can reduce the larger pile from Template:Math stones to Template:Math stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.<ref>Template:Harvnb</ref><ref>Template:Cite book</ref>

Mathematical applicationsEdit

Bézout's identityEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Bézout's identity states that the greatest common divisor Template:Math of two integers Template:Math and Template:Math can be represented as a linear sum of the original two numbers Template:Math and Template:Math.<ref>Template:Cite book</ref> In other words, it is always possible to find integers Template:Math and Template:Math such that Template:Math.<ref>Template:Harvnb</ref><ref>Template:Harvnb</ref>

The integers Template:Math and Template:Math can be calculated from the quotients Template:Math, Template:Math, etc. by reversing the order of equations in Euclid's algorithm.<ref>Template:Harvnb</ref> Beginning with the next-to-last equation, Template:Math can be expressed in terms of the quotient Template:Math and the two preceding remainders, Template:Math and Template:Math:

Template:Math.

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

Template:Math and

Template:Math.

Substituting these formulae for Template:Math and Template:Math into the first equation yields Template:Math as a linear sum of the remainders Template:Math and Template:Math. The process of substituting remainders by formulae involving their predecessors can be continued until the original numbers Template:Math and Template:Math are reached:

Template:Math

Template:Math.

After all the remainders Template:Math, Template:Math, etc. have been substituted, the final equation expresses Template:Math as a linear sum of Template:Math and Template:Math, so that Template:Math.

The Euclidean algorithm, and thus Bézout's identity, can be generalized to the context of Euclidean domains.

Principal ideals and related problemsEdit

Bézout's identity provides yet another definition of the greatest common divisor Template:Math of two numbers Template:Math and Template:Math.<ref name="Leveque_p33" >Template:Harvnb</ref> Consider the set of all numbers Template:Math, where Template:Math and Template:Math are any two integers. Since Template:Math and Template:Math are both divisible by Template:Math, every number in the set is divisible by Template:Math. In other words, every number of the set is an integer multiple of Template:Math. This is true for every common divisor of Template:Math and Template:Math. However, unlike other common divisors, the greatest common divisor is a member of the set; by Bézout's identity, choosing Template:Math and Template:Math gives Template:Math. A smaller common divisor cannot be a member of the set, since every member of the set must be divisible by Template:Math. Conversely, any multiple Template:Math of Template:Math can be obtained by choosing Template:Math and Template:Math, where Template:Math and Template:Math are the integers of Bézout's identity. This may be seen by multiplying Bézout's identity by m,

Template:Math.

Therefore, the set of all numbers Template:Math is equivalent to the set of multiples Template:Math of Template:Math. In other words, the set of all possible sums of integer multiples of two numbers (Template:Math and Template:Math) is equivalent to the set of multiples of Template:Math. The GCD is said to be the generator of the ideal of Template:Math and Template:Math. This GCD definition led to the modern abstract algebraic concepts of a principal ideal (an ideal generated by a single element) and a principal ideal domain (a domain in which every ideal is a principal ideal).

Certain problems can be solved using this result.<ref>Template:Harvnb</ref> For example, consider two measuring cups of volume Template:Math and Template:Math. By adding/subtracting Template:Math multiples of the first cup and Template:Math multiples of the second cup, any volume Template:Math can be measured out. These volumes are all multiples of Template:Math.

Extended Euclidean algorithmEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

The integers Template:Math and Template:Math of Bézout's identity can be computed efficiently using the extended Euclidean algorithm. This extension adds two recursive equations to Euclid's algorithm<ref>Template:Harvnb</ref>

Template:Math

with the starting values

Template:Math

Template:Math.

Using this recursion, Bézout's integers Template:Math and Template:Math are given by Template:Math and Template:Math, where Template:Math is the step on which the algorithm terminates with Template:Math.

The validity of this approach can be shown by induction. Assume that the recursion formula is correct up to step Template:Math of the algorithm; in other words, assume that

Template:Math

for all Template:Math less than Template:Math. The Template:Mathth step of the algorithm gives the equation

Template:Math.

Since the recursion formula has been assumed to be correct for Template:Math and Template:Math, they may be expressed in terms of the corresponding Template:Math and Template:Math variables

Template:Math.

Rearranging this equation yields the recursion formula for step Template:Math, as required

Template:Math.

Matrix methodEdit

The integers Template:Math and Template:Math can also be found using an equivalent matrix method.<ref name="Koshy_2002">Template:Cite book</ref> The sequence of equations of Euclid's algorithm

<math>

\begin{align} a & = q_0 b + r_0 \\ b & = q_1 r_0 + r_1 \\ & \,\,\,\vdots \\ r_{N-2} & = q_N r_{N-1} + 0 \end{align} </math> can be written as a product of Template:Math quotient matrices multiplying a two-dimensional remainder vector

<math>

\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} b \\ r_0 \end{pmatrix} = \begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_0 \\ r_1 \end{pmatrix} = \cdots = \prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} \,. </math>

Let Template:Math represent the product of all the quotient matrices

<math>

\mathbf{M} = \begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix} = \prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} q_{N} & 1 \\ 1 & 0 \end{pmatrix} \,. </math>

This simplifies the Euclidean algorithm to the form

<math>

\begin{pmatrix} a \\ b \end{pmatrix} = \mathbf{M} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} = \mathbf{M} \begin{pmatrix} g \\ 0 \end{pmatrix} \,. </math>

To express Template:Math as a linear sum of Template:Math and Template:Math, both sides of this equation can be multiplied by the inverse of the matrix Template:Math.<ref name="Koshy_2002" /><ref name="Bach_1996">Template:Cite book</ref> The determinant of Template:Math equals Template:Math, since it equals the product of the determinants of the quotient matrices, each of which is negative one. Since the determinant of Template:Math is never zero, the vector of the final remainders can be solved using the inverse of Template:Math

<math>

\begin{pmatrix} g \\ 0 \end{pmatrix} = \mathbf{M}^{-1} \begin{pmatrix} a \\ b \end{pmatrix} = (-1)^{N+1} \begin{pmatrix} m_{22} & -m_{12} \\ -m_{21} & m_{11} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} \,. </math>

Since the top equation gives

Template:Math,

the two integers of Bézout's identity are Template:Math and Template:Math. The matrix method is as efficient as the equivalent recursion, with two multiplications and two additions per step of the Euclidean algorithm.

Euclid's lemma and unique factorizationEdit

Bézout's identity is essential to many applications of Euclid's algorithm, such as demonstrating the unique factorization of numbers into prime factors.<ref>Template:Harvnb</ref> To illustrate this, suppose that a number Template:Math can be written as a product of two factors Template:Math and Template:Math, that is, Template:Math. If another number Template:Math also divides Template:Math but is coprime with Template:Math, then Template:Math must divide Template:Math, by the following argument: If the greatest common divisor of Template:Math and Template:Math is Template:Math, then integers Template:Math and Template:Math can be found such that

Template:Math

by Bézout's identity. Multiplying both sides by Template:Math gives the relation:

Template:Math

Since Template:Math divides both terms on the right-hand side, it must also divide the left-hand side, Template:Math. This result is known as Euclid's lemma.<ref name="Ore, p. 44">Template:Harvnb</ref> Specifically, if a prime number divides Template:Math, then it must divide at least one factor of Template:Math. Conversely, if a number Template:Math is coprime to each of a series of numbers Template:Math, Template:Math, ..., Template:Math, then Template:Math is also coprime to their product, Template:Math.<ref name="Ore, p. 44"/>

Euclid's lemma suffices to prove that every number has a unique factorization into prime numbers.<ref>Template:Harvnb</ref> To see this, assume the contrary, that there are two independent factorizations of Template:Math into Template:Math and Template:Math prime factors, respectively

Template:Math.

Since each prime Template:Math divides Template:Math by assumption, it must also divide one of the Template:Math factors; since each Template:Math is prime as well, it must be that Template:Math. Iteratively dividing by the Template:Math factors shows that each Template:Math has an equal counterpart Template:Math; the two prime factorizations are identical except for their order. The unique factorization of numbers into primes has many applications in mathematical proofs, as shown below.

Linear Diophantine equationsEdit

File:Diophante Bezout.svg

Plot of a linear Diophantine equation, Template:Math. The solutions are shown as blue circles.

Diophantine equations are equations in which the solutions are restricted to integers; they are named after the 3rd-century Alexandrian mathematician Diophantus.<ref>Template:Harvnb</ref> A typical linear Diophantine equation seeks integers Template:Math and Template:Math such that<ref>Template:Harvnb</ref>

Template:Math

where Template:Math, Template:Math and Template:Math are given integers. This can be written as an equation for Template:Math in modular arithmetic:

Template:Math.

Let Template:Math be the greatest common divisor of Template:Math and Template:Math. Both terms in Template:Math are divisible by Template:Math; therefore, Template:Math must also be divisible by Template:Math, or the equation has no solutions. By dividing both sides by Template:Math, the equation can be reduced to Bezout's identity

Template:Math,

where Template:Math and Template:Math can be found by the extended Euclidean algorithm.<ref>Template:Harvnb</ref> This provides one solution to the Diophantine equation, Template:Math and Template:Math.

In general, a linear Diophantine equation has no solutions, or an infinite number of solutions.<ref>Template:Harvnb</ref> To find the latter, consider two solutions, Template:Math and Template:Math, where

Template:Math

or equivalently

Template:Math.

Therefore, the smallest difference between two Template:Math solutions is Template:Math, whereas the smallest difference between two Template:Math solutions is Template:Math. Thus, the solutions may be expressed as

Template:Math

Template:Math.

By allowing Template:Math to vary over all possible integers, an infinite family of solutions can be generated from a single solution Template:Math. If the solutions are required to be positive integers Template:Math, 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;<ref>Template:Harvnb</ref> this is impossible for a system of linear equations when the solutions can be any real number (see Underdetermined system).

Multiplicative inverses and the RSA algorithmEdit

A finite field is a set of numbers with four generalized operations. The operations are called addition, subtraction, multiplication and division and have their usual properties, such as commutativity, associativity and distributivity. An example of a finite field is the set of 13 numbers Template:Math using modular arithmetic. In this field, the results of any mathematical operation (addition, subtraction, multiplication, or division) is reduced modulo Template:Math; that is, multiples of Template:Math are added or subtracted until the result is brought within the range Template:Math–Template:Math. For example, the result of Template:Math. Such finite fields can be defined for any prime Template:Math; using more sophisticated definitions, they can also be defined for any power Template:Math of a prime Template:Math. Finite fields are often called Galois fields, and are abbreviated as Template:Math or Template:Math).

In such a field with Template:Math numbers, every nonzero element Template:Math has a unique modular multiplicative inverse, Template:Math such that Template:Math. This inverse can be found by solving the congruence equation Template:Math,<ref>Template:Harvnb</ref> or the equivalent linear Diophantine equation<ref>Template:Harvnb</ref>

Template:Math.

This equation can be solved by the Euclidean algorithm, as described above. Finding multiplicative inverses is an essential step in the RSA algorithm, which is widely used in electronic commerce; specifically, the equation determines the integer used to decrypt the message.<ref>Template:Harvnb</ref> Although the RSA algorithm uses rings rather than fields, the Euclidean algorithm can still be used to find a multiplicative inverse where one exists. The Euclidean algorithm also has other applications in error-correcting codes; for example, it can be used as an alternative to the Berlekamp–Massey algorithm for decoding BCH and Reed–Solomon codes, which are based on Galois fields.<ref>Template:Cite book</ref>

Chinese remainder theoremEdit

Euclid's algorithm can also be used to solve multiple linear Diophantine equations.<ref>Template:Harvnb</ref> Such equations arise in the Chinese remainder theorem, which describes a novel method to represent an integer x. Instead of representing an integer by its digits, it may be represented by its remainders x_i modulo a set of N coprime numbers m_i:<ref>Template:Harvnb</ref>

<math>

\begin{align} x_1 & \equiv x \pmod {m_1} \\ x_2 & \equiv x \pmod {m_2} \\ & \,\,\,\vdots \\ x_N & \equiv x \pmod {m_N} \,. \end{align} </math>

The goal is to determine x from its N remainders x_i. The solution is to combine the multiple equations into a single linear Diophantine equation with a much larger modulus M that is the product of all the individual moduli m_i, and define M_i as

Thus, each M_i is the product of all the moduli except m_i. The solution depends on finding N new numbers h_i such that

<math> M_i h_i \equiv 1 \pmod {m_i} \,. </math>

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

<math> x \equiv (x_1 M_1 h_1 + x_2 M_2 h_2 + \cdots + x_N M_N h_N) \pmod M \,.</math>

Since these numbers h_i are the multiplicative inverses of the M_i, they may be found using Euclid's algorithm as described in the previous subsection.

Stern–Brocot treeEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} The Euclidean algorithm can be used to arrange the set of all positive rational numbers into an infinite binary search tree, called the Stern–Brocot tree. The number 1 (expressed as a fraction 1/1) is placed at the root of the tree, and the location of any other number a/b can be found by computing gcd(a,b) using the original form of the Euclidean algorithm, in which each step replaces the larger of the two given numbers by its difference with the smaller number (not its remainder), stopping when two equal numbers are reached. A step of the Euclidean algorithm that replaces the first of the two numbers corresponds to a step in the tree from a node to its right child, and a step that replaces the second of the two numbers corresponds to a step in the tree from a node to its left child. The sequence of steps constructed in this way does not depend on whether a/b is given in lowest terms, and forms a path from the root to a node containing the number a/b.<ref>Template:Cite book</ref> 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:

File:SternBrocotTree.svg

The Stern–Brocot tree, and the Stern–Brocot sequences of order i for i = 1, 2, 3, 4

<math>

\begin{align}

& \gcd(3,4) & \leftarrow \\

= {} & \gcd(3,1) & \rightarrow \\ = {} & \gcd(2,1) & \rightarrow \\ = {} & \gcd(1,1). \end{align} </math>

The Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called the Calkin–Wilf tree. The difference is that the path is reversed: instead of producing a path from the root of the tree to a target, it produces a path from the target to the root.

Continued fractionsEdit

The Euclidean algorithm has a close relationship with continued fractions.<ref name="Vinogradov_1954">Template:Cite book</ref> The sequence of equations can be written in the form

<math>

\begin{align} \frac a b &= q_0 + \frac{r_0} b \\ \frac b {r_0} &= q_1 + \frac{r_1}{r_0} \\ \frac{r_0}{r_1} &= q_2 + \frac{r_2}{r_1} \\ & \,\,\, \vdots \\ \frac{r_{k-2}}{r_{k-1}} &= q_k + \frac{r_k}{r_{k-1}} \\ & \,\,\, \vdots \\ \frac{r_{N-2}}{r_{N-1}} &= q_N\,. \end{align} </math>

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

<math>\frac a b = q_0 + \cfrac 1 {q_1 + \cfrac{r_1}{r_0}} \,.</math>

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

<math>\frac a b = q_0 + \cfrac 1 {q_1 + \cfrac 1 {q_2 + \cfrac{r_2}{r_1}}}\,. </math>

The final ratio of remainders r_k/r_k−1 can always be replaced using the next equation in the series, up to the final equation. The result is a continued fraction

<math>\frac a b = q_0 + \cfrac 1 {q_1 + \cfrac 1 {q_2 + \cfrac{1}{\ddots + \cfrac 1 {q_N}}}} = [ q_0; q_1, q_2, \ldots , q_N ] \,.</math>

In the worked example above, the gcd(1071, 462) was calculated, and the quotients q_k were 2, 3 and 7, respectively. Therefore, the fraction 1071/462 may be written

<math>\frac{1071}{462} = 2 + \cfrac 1 {3 + \cfrac 1 7} = [2; 3, 7]</math>

as can be confirmed by calculation.

Factorization algorithmsEdit

Calculating a greatest common divisor is an essential step in several integer factorization algorithms,<ref>Template:Harvnb, pp. 225–349</ref> such as Pollard's rho algorithm,<ref>Template:Harvnb, pp. 369–371</ref> Shor's algorithm,<ref>Template:Cite journal</ref> Dixon's factorization method<ref>Template:Cite journal</ref> and the Lenstra elliptic curve factorization.<ref>Template:Cite journal</ref> The Euclidean algorithm may be used to find this GCD efficiently. Continued fraction factorization uses continued fractions, which are determined using Euclid's algorithm.<ref>Template:Harvnb, pp. 380–384</ref>

Algorithmic efficiencyEdit

File:Euclidean Algorithm Running Time.svg

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.

The computational efficiency of Euclid's algorithm has been studied thoroughly.<ref>Template:Harvnb, pp. 339–364</ref> This efficiency can be described by the number of division steps the algorithm requires, multiplied by the computational expense of each step. The first known analysis of Euclid's algorithm is due to A. A. L. Reynaud in 1811,<ref>Template:Cite book As cited by Template:Harvtxt.</ref> who showed that the number of division steps on input (u, v) is bounded by v; later he improved this to v/2 + 2. Later, in 1841, P. J. E. Finck showed<ref>Template:Cite book</ref> that the number of division steps is at most 2 log₂ v + 1, and hence Euclid's algorithm runs in time polynomial in the size of the input.Template:Sfn Émile Léger, in 1837, studied the worst case, which is when the inputs are consecutive Fibonacci numbers.Template:Sfn Finck's analysis was refined by Gabriel Lamé in 1844,<ref>Template:Cite journal</ref> 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.<ref>Template:Cite journal</ref><ref>Template:Cite book</ref>

In the uniform cost model (suitable for analyzing the complexity of gcd calculation on numbers that fit into a single machine word), each step of the algorithm takes constant time, and Lamé's analysis implies that the total running time is also O(h). However, in a model of computation suitable for computation with larger numbers, the computational expense of a single remainder computation in the algorithm can be as large as O(h²).<ref name="Knuth-257-261"/> In this case the total time for all of the steps of the algorithm can be analyzed using a telescoping series, showing that it is also O(h²). Modern algorithmic techniques based on the Schönhage–Strassen algorithm for fast integer multiplication can be used to speed this up, leading to quasilinear algorithms for the GCD.<ref name="Crandall_2001" /><ref name="Moller08"/>

Number of stepsEdit

The number of steps to calculate the GCD of two natural numbers, a and b, may be denoted by T(a, b).<ref name="Knuth, p. 344">Template:Harvnb, p. 344</ref> If g is the GCD of a and b, then a = mg and b = ng for two coprime numbers m and n. Then

Template:Math

as may be seen by dividing all the steps in the Euclidean algorithm by g.<ref>Template:Harvnb</ref> By the same argument, the number of steps remains the same if a and b are multiplied by a common factor w: T(a, b) = T(wa, wb). Therefore, the number of steps T may vary dramatically between neighboring pairs of numbers, such as T(a, b) and T(a, b + 1), depending on the size of the two GCDs.

The recursive nature of the Euclidean algorithm gives another equation

Template:Math

where T(x, 0) = 0 by assumption.<ref name="Knuth, p. 344"/>

Worst-caseEdit

If the Euclidean algorithm requires N steps for a pair of natural numbers a > b > 0, the smallest values of a and b for which this is true are the Fibonacci numbers F_N+2 and F_N+1, respectively.<ref name="Knuth, p. 343">Template:Harvnb, p. 343</ref> More precisely, if the Euclidean algorithm requires N steps for the pair a > b, then one has a ≥ F_N+2 and b ≥ F_N+1. This can be shown by induction.<ref>Template:Harvnb</ref> If N = 1, b divides a with no remainder; the smallest natural numbers for which this is true is b = 1 and a = 2, which are F₂ and F₃, respectively. Now assume that the result holds for all values of N up to M − 1. The first step of the M-step algorithm is a = q₀b + r₀, and the Euclidean algorithm requires M − 1 steps for the pair b > r₀. By induction hypothesis, one has b ≥ F_M+1 and r₀ ≥ F_M. Therefore, a = q₀b + r₀ ≥ b + r₀ ≥ F_M+1 + F_M = F_M+2, which is the desired inequality. This proof, published by Gabriel Lamé in 1844, represents the beginning of computational complexity theory,<ref>Template:Harvnb</ref> and also the first practical application of the Fibonacci numbers.<ref name="Knuth, p. 343"/>

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).<ref>Template:Harvnb</ref> For if the algorithm requires N steps, then b is greater than or equal to F_N+1 which in turn is greater than or equal to φ^N−1, where φ is the golden ratio. Since b ≥ φ^N−1, then N − 1 ≤ log_φb. Since log₁₀φ > 1/5, (N − 1)/5 < log₁₀φ log_φb = log₁₀b. Thus, N ≤ 5 log₁₀b. Thus, the Euclidean algorithm always needs less than O(h) divisions, where h is the number of digits in the smaller number b.

AverageEdit

The average number of steps taken by the Euclidean algorithm has been defined in three different ways. The first definition is the average time T(a) required to calculate the GCD of a given number a and a smaller natural number b chosen with equal probability from the integers 0 to a − 1<ref name="Knuth, p. 344"/>

<math>T(a) = \frac 1 a \sum_{0 \leq b<a} T(a, b).

</math>

However, since T(a, b) fluctuates dramatically with the GCD of the two numbers, the averaged function T(a) is likewise "noisy".<ref>Template:Harvnb, p. 353</ref>

To reduce this noise, a second average τ(a) is taken over all numbers coprime with a

<math>\tau(a) = \frac 1 {\varphi(a)} \sum_{\begin{smallmatrix} 0 \leq b<a \\ \gcd(a, b) = 1 \end{smallmatrix}} T(a, b).

</math>

There are φ(a) coprime integers less than a, where φ is Euler's totient function. This tau average grows smoothly with a<ref>Template:Harvnb, p. 357</ref><ref>Template:Cite journal</ref>

<math>\tau(a) = \frac{12}{\pi^2}\ln 2 \ln a + C + O(a^{-1/6-\varepsilon})</math>

with the residual error being of order a^−(1/6)+ε, where ε is infinitesimal. The constant C in this formula is called Porter's constant<ref> Template:Cite journal</ref> and equals

<math>C= -\frac 1 2 + \frac{6 \ln 2}{\pi^2}\left(4\gamma -\frac{24}{\pi^2}\zeta'(2) + 3\ln 2 - 2\right) \approx 1.467</math>

where Template:Math is the Euler–Mascheroni constant and Template:Math is the derivative of the Riemann zeta function.<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref> The leading coefficient (12/π²) ln 2 was determined by two independent methods.<ref>Template:Cite journal</ref><ref>Template:Cite book</ref>

Since the first average can be calculated from the tau average by summing over the divisors d of a<ref>Template:Harvnb, p. 354</ref>

<math> T(a) = \frac 1 a \sum_{d \mid a} \varphi(d) \tau(d)

</math> it can be approximated by the formula<ref name="Norton_1990">Template:Cite journal</ref>

<math>T(a) \approx C + \frac{12}{\pi^2} \ln 2\, \biggl({\ln a} - \sum_{d \mid a} \frac{\Lambda(d)} d\biggr)</math>

where Λ(d) is the Mangoldt function.<ref>Template:Harvnb, p. 355</ref>

A third average Y(n) is defined as the mean number of steps required when both a and b are chosen randomly (with uniform distribution) from 1 to n<ref name="Norton_1990" />

<math>Y(n) = \frac 1 {n^2} \sum_{a=1}^n \sum_{b=1}^n T(a, b) = \frac 1 n \sum_{a=1}^n T(a).

</math>

Substituting the approximate formula for T(a) into this equation yields an estimate for Y(n)<ref>Template:Harvnb, p. 356</ref>

<math>Y(n) \approx \frac{12}{\pi^2} \ln 2 \ln n + 0.06.</math>

Computational expense per stepEdit

In each step k of the Euclidean algorithm, the quotient q_k and remainder r_k are computed for a given pair of integers r_k−2 and r_k−1

Template:Math

The computational expense per step is associated chiefly with finding q_k, since the remainder r_k can be calculated quickly from r_k−2, r_k−1, and q_k

Template:Math

The computational expense of dividing h-bit numbers scales as Template:Math, where Template:Mvar is the length of the quotient.<ref name="Knuth-257-261">Template:Harvnb, pp. 257–261</ref>

For comparison, Euclid's original subtraction-based algorithm can be much slower. A single integer division is equivalent to the quotient q number of subtractions. If the ratio of a and b is very large, the quotient is large and many subtractions will be required. On the other hand, it has been shown that the quotients are very likely to be small integers. The probability of a given quotient q is approximately Template:Math where Template:Math.<ref>Template:Harvnb, p. 352</ref> 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,<ref>Template:Cite book</ref> the subtraction-based Euclid's algorithm is competitive with the division-based version.<ref>Template:Harvnb</ref> This is exploited in the binary version of Euclid's algorithm.<ref>Template:Harvnb</ref>

Combining the estimated number of steps with the estimated computational expense per step shows that the Euclid's algorithm grows quadratically (h²) with the average number of digits h in the initial two numbers a and b. Let Template:Math represent the number of digits in the successive remainders Template:Math. Since the number of steps N grows linearly with h, the running time is bounded by

<math>

O\Big(\sum_{i<N}h_i(h_i-h_{i+1}+2)\Big)\subseteq O\Big(h\sum_{i<N}(h_i-h_{i+1}+2) \Big) \subseteq O(h(h_0+2N))\subseteq O(h^2).</math>

Alternative methodsEdit

Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity.<ref> Template:Cite book</ref> For comparison, the efficiency of alternatives to Euclid's algorithm may be determined.

One inefficient approach to finding the GCD of two natural numbers a and b is to calculate all their common divisors; the GCD is then the largest common divisor. The common divisors can be found by dividing both numbers by successive integers from 2 to the smaller number b. The number of steps of this approach grows linearly with b, or exponentially in the number of digits. Another inefficient approach is to find the prime factors of one or both numbers. As noted above, the GCD equals the product of the prime factors shared by the two numbers a and b.<ref name="Schroeder_21" /> Present methods for prime factorization are also inefficient; many modern cryptography systems even rely on that inefficiency.<ref name="Schroeder_216" />

The binary GCD algorithm is an efficient alternative that substitutes division with faster operations by exploiting the binary representation used by computers.<ref>Template:Harvnb, pp. 321–323</ref><ref>Template:Cite journal</ref> However, this alternative also scales like O(h²). It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way.<ref name="Crandall_2001">Template:Harvnb, pp. 77–79, 81–85, 425–431</ref> Additional efficiency can be gleaned by examining only the leading digits of the two numbers a and b.<ref>Template:Harvnb, p. 328</ref><ref>Template:Cite journal</ref> The binary algorithm can be extended to other bases (k-ary algorithms),<ref>Template:Cite journal</ref> with up to fivefold increases in speed.<ref>Template:Cite journal</ref> Lehmer's GCD algorithm uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases.

A recursive approach for very large integers (with more than 25,000 digits) leads to quasilinear integer GCD algorithms,<ref>Template:Cite book</ref> such as those of Schönhage,<ref>Template:Cite journal</ref><ref>Template:Cite book</ref> and Stehlé and Zimmermann.<ref>Template:Cite book</ref> These algorithms exploit the 2×2 matrix form of the Euclidean algorithm given above. These quasilinear methods generally scale as Template:Math<ref name="Crandall_2001" /><ref name="Moller08">Template:Cite journal</ref>

GeneralizationsEdit

Although the Euclidean algorithm is used to find the greatest common divisor of two natural numbers (positive integers), it may be generalized to the real numbers, and to other mathematical objects, such as polynomials,<ref name="Lang_1984"/> quadratic integers<ref name="weinberger"/> and Hurwitz quaternions.<ref name="stillwell151-152"/> In the latter cases, the Euclidean algorithm is used to demonstrate the crucial property of unique factorization, i.e., that such numbers can be factored uniquely into irreducible elements, the counterparts of prime numbers. Unique factorization is essential to many proofs of number theory.

Rational and real numbersEdit

Euclid's algorithm can be applied to real numbers, as described by Euclid in Book 10 of his Elements. The goal of the algorithm is to identify a real number Template:Mvar such that two given real numbers, Template:Mvar and Template:Mvar, are integer multiples of it: Template:Math and Template:Math, where Template:Mvar and Template:Mvar are integers.<ref name="Weil_1983" /> This identification is equivalent to finding an integer relation among the real numbers Template:Mvar and Template:Mvar; that is, it determines integers Template:Mvar and Template:Mvar such that Template:Math. If such an equation is possible, a and b are called commensurable lengths, otherwise they are incommensurable lengths.<ref>Template:Cite book</ref><ref>Template:Cite book Reprinted, Dover Publications, 2004, Template:Isbn</ref>

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

and can be written as a finite continued fraction Template:Math. If the algorithm does not stop, the fraction Template:Math is an irrational number and can be described by an infinite continued fraction Template:Math.<ref>Template:Cite book</ref> Examples of infinite continued fractions are the golden ratio Template:Math and the square root of two, Template:Math.<ref>Template:Cite book</ref> The algorithm is unlikely to stop, since almost all ratios Template:Math of two real numbers are irrational.<ref>Template:Cite book</ref>

An infinite continued fraction may be truncated at a step Template:Math to yield an approximation to Template:Math that improves as Template:Mvar is increased. The approximation is described by convergents Template:Math; the numerator and denominators are coprime and obey the recurrence relation

<math>\begin{align}

  m_k &= q_k m_{k-1} + m_{k-2} \\
  n_k &= q_k n_{k-1} + n_{k-2},
\end{align}</math>

where Template:Math and Template:Math are the initial values of the recursion. The convergent Template:Math is the best rational number approximation to Template:Math with denominator Template:Math:<ref>Template:Cite book</ref>

<math> \left|\frac{a}{b} - \frac{m_k}{n_k}\right| < \frac{1}{n_k^2}.</math>

PolynomialsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Polynomials in a single variable x can be added, multiplied and factored into irreducible polynomials, which are the analogs of the prime numbers for integers. The greatest common divisor polynomial Template:Math of two polynomials Template:Math and Template:Math is defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm.<ref name="Lang_1984" >Template:Cite book</ref> The basic procedure is similar to that for integers. At each step Template:Mvar, a quotient polynomial Template:Math and a remainder polynomial Template:Math are identified to satisfy the recursive equation

where Template:Math and Template:Math. 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: Template:Math. 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, Template:Math and Template:Math.<ref>Template:Harvnb</ref>

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

<math>\begin{align}

  a(x) &= x^4 - 4x^3 + 4x^2 - 3x + 14 = (x^2 - 5x + 7)(x^2 + x + 2) \qquad \text{and}\\
  b(x) &= x^4 + 8x^3 + 12x^2 + 17x + 6 = (x^2 + 7x + 3)(x^2 + x + 2).
\end{align}</math>

Dividing Template:Math by Template:Math yields a remainder Template:Math. In the next step, Template:Math is divided by Template:Math yielding a remainder Template:Math. Finally, dividing Template:Math by Template:Math yields a zero remainder, indicating that Template:Math is the greatest common divisor polynomial of Template:Math and Template:Math, consistent with their factorization.

Many of the applications described above for integers carry over to polynomials.<ref>Template:Harvnb</ref> The Euclidean algorithm can be used to solve linear Diophantine equations and Chinese remainder problems for polynomials; continued fractions of polynomials can also be defined.

The polynomial Euclidean algorithm has other applications, such as Sturm chains, a method for counting the zeros of a polynomial that lie inside a given real interval.<ref>Template:Cite book</ref> This in turn has applications in several areas, such as the Routh–Hurwitz stability criterion in control theory.<ref>Template:Cite book</ref>

Finally, the coefficients of the polynomials need not be drawn from integers, real numbers or even the complex numbers. For example, the coefficients may be drawn from a general field, such as the finite fields Template:Math described above. The corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.<ref name="Lang_1984" />

Gaussian integersEdit

File:Gaussian primes.svg

Distribution of Gaussian primes Template:Math in the complex plane, with norms Template:Math less than 500

The Gaussian integers are complex numbers of the form Template:Math, where Template:Mvar and Template:Mvar are ordinary integers<ref group=note>The phrase "ordinary integer" is commonly used for distinguishing usual integers from Gaussian integers, and more generally from algebraic integers.</ref> and Template:Mvar is the square root of negative one.<ref name="Stillwell_2003" /> By defining an analog of the Euclidean algorithm, Gaussian integers can be shown to be uniquely factorizable, by the argument above.<ref name="Gauss_1832">Template:Cite journal Reprinted in Template:Cite book and Template:Cite book</ref> This unique factorization is helpful in many applications, such as deriving all Pythagorean triples or proving Fermat's theorem on sums of two squares.<ref name="Stillwell_2003">Template:Harvnb</ref> In general, the Euclidean algorithm is convenient in such applications, but not essential; for example, the theorems can often be proven by other arguments.

The Euclidean algorithm developed for two Gaussian integers Template:Mvar and Template:Mvar is nearly the same as that for ordinary integers,<ref name="hensley">Template:Cite book</ref> but differs in two respects. As before, we set Template:Math and Template:Math, and the task at each step Template:Mvar is to identify a quotient Template:Math and a remainder Template:Math such that

where every remainder is strictly smaller than its predecessor: Template:Math. The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are complex numbers. The quotients Template:Math are generally found by rounding the real and complex parts of the exact ratio (such as the complex number Template:Math) to the nearest integers.<ref name="hensley"/> The second difference lies in the necessity of defining how one complex remainder can be "smaller" than another. To do this, a norm function Template:Math is defined, which converts every Gaussian integer Template:Math into an ordinary integer. After each step Template:Mvar of the Euclidean algorithm, the norm of the remainder Template:Math is smaller than the norm of the preceding remainder, Template:Math. 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.<ref>Template:Cite book</ref> The final nonzero remainder is Template:Math, the Gaussian integer of largest norm that divides both Template:Mvar and Template:Mvar; it is unique up to multiplication by a unit, Template:Math or Template:Math.<ref>Template:Cite book</ref>

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;<ref>Template:Cite book</ref> continued fractions of Gaussian integers can also be defined.<ref name="hensley"/>

Euclidean domainsEdit

A set of elements under two binary operations, denoted as addition and multiplication, is called a Euclidean domain if it forms a commutative ring Template:Mvar and, roughly speaking, if a generalized Euclidean algorithm can be performed on them.<ref>Template:Harvnb</ref><ref>Template:Harvnb</ref> The two operations of such a ring need not be the addition and multiplication of ordinary arithmetic; rather, they can be more general, such as the operations of a mathematical group or monoid. Nevertheless, these general operations should respect many of the laws governing ordinary arithmetic, such as commutativity, associativity and distributivity.

The generalized Euclidean algorithm requires a Euclidean function, i.e., a mapping Template:Mvar from Template:Mvar into the set of nonnegative integers such that, for any two nonzero elements Template:Mvar and Template:Mvar in Template:Mvar, there exist Template:Mvar and Template:Mvar in Template:Mvar such that Template:Math and Template:Math.<ref>Template:Cite book</ref> Examples of such mappings are the absolute value for integers, the degree for univariate polynomials, and the norm for Gaussian integers above.<ref>Template:Harvtxt, p. 132</ref><ref>Template:Harvtxt, p. 161</ref> The basic principle is that each step of the algorithm reduces f inexorably; hence, if Template:Mvar can be reduced only a finite number of times, the algorithm must stop in a finite number of steps. This principle relies on the well-ordering property of the non-negative integers, which asserts that every non-empty set of non-negative integers has a smallest member.<ref name="sharpe">Template:Cite book</ref>

The fundamental theorem of arithmetic applies to any Euclidean domain: Any number from a Euclidean domain can be factored uniquely into irreducible elements. Any Euclidean domain is a unique factorization domain (UFD), although the converse is not true.<ref name="sharpe"/> The Euclidean domains and the UFD's are subclasses of the GCD domains, domains in which a greatest common divisor of two numbers always exists.<ref>Template:Harvtxt, p. 52</ref> In other words, a greatest common divisor may exist (for all pairs of elements in a domain), although it may not be possible to find it using a Euclidean algorithm. A Euclidean domain is always a principal ideal domain (PID), an integral domain in which every ideal is a principal ideal.<ref>Template:Harvtxt, p. 131</ref> Again, the converse is not true: not every PID is a Euclidean domain.

The unique factorization of Euclidean domains is useful in many applications. For example, the unique factorization of the Gaussian integers is convenient in deriving formulae for all Pythagorean triples and in proving Fermat's theorem on sums of two squares.<ref name="Stillwell_2003" /> Unique factorization was also a key element in an attempted proof of Fermat's Last Theorem published in 1847 by Gabriel Lamé, the same mathematician who analyzed the efficiency of Euclid's algorithm, based on a suggestion of Joseph Liouville.<ref>Template:Cite journal</ref> Lamé's approach required the unique factorization of numbers of the form Template:Math, where Template:Mvar and Template:Mvar are integers, and Template:Math is an Template:Mvarth root of 1, that is, Template:Math. Although this approach succeeds for some values of Template:Mvar (such as Template:Math, the Eisenstein integers), in general such numbers do Template:Em factor uniquely. This failure of unique factorization in some cyclotomic fields led Ernst Kummer to the concept of ideal numbers and, later, Richard Dedekind to ideals.<ref>Template:Cite book</ref>

Unique factorization of quadratic integersEdit

File:Eisenstein primes.svg

Distribution of Eisenstein primes Template:Math in the complex plane, with norms less than 500. The number Template:Mvar is a cube root of 1.

The quadratic integer rings are helpful to illustrate Euclidean domains. Quadratic integers are generalizations of the Gaussian integers in which the imaginary unit i is replaced by a number Template:Mvar. Thus, they have the form Template:Math, where Template:Mvar and Template:Mvar are integers and Template:Mvar has one of two forms, depending on a parameter Template:Mvar. If Template:Mvar does not equal a multiple of four plus one, then

<math>\omega = \sqrt D .</math>

If, however, Template:Math does equal a multiple of four plus one, then

<math>\omega = \frac{1 + \sqrt{D}}{2} .</math>

If the function Template:Mvar corresponds to a norm function, such as that used to order the Gaussian integers above, then the domain is known as norm-Euclidean. The norm-Euclidean rings of quadratic integers are exactly those where Template:Mvar 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.<ref>Template:Harvnb</ref><ref>Template:Cite book</ref> The cases Template:Math and Template:Math yield the Gaussian integers and Eisenstein integers, respectively.

If Template:Mvar is allowed to be any Euclidean function, then the list of possible values of Template:Mvar for which the domain is Euclidean is not yet known.<ref name="Clark_1994">Template:Cite journal</ref> The first example of a Euclidean domain that was not norm-Euclidean (with Template:Math) was published in 1994.<ref name="Clark_1994" /> In 1973, Weinberger proved that a quadratic integer ring with Template:Math is Euclidean if, and only if, it is a principal ideal domain, provided that the generalized Riemann hypothesis holds.<ref name="weinberger">Template:Cite journal</ref>

Noncommutative ringsEdit

The Euclidean algorithm may be applied to some noncommutative rings such as the set of Hurwitz quaternions.<ref name="stillwell151-152">Template:Harvnb</ref><ref name=bgv>Template:Harvtxt; 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.</ref> Let Template:Mvar and Template:Mvar represent two elements from such a ring. They have a common right divisor Template:Mvar if Template:Math and Template:Math for some choice of Template:Mvar and Template:Mvar in the ring. Similarly, they have a common left divisor if Template:Math and Template:Math for some choice of Template:Mvar and Template:Mvar 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.<ref name="stillwell151-152"/><ref name=bgv/> Choosing the right divisors, the first step in finding the Template:Math by the Euclidean algorithm can be written

<math>\rho_0 = \alpha - \psi_0\beta = (\xi - \psi_0\eta)\delta,</math>

where Template:Math represents the quotient and Template:Math the remainder. Here the quotient and remainder are chosen so that (if nonzero) the remainder has Template:Math for a "Euclidean function" N defined analogously to the Euclidean functions of Euclidean domains in the non-commutative case.<ref name=bgv/> This equation shows that any common right divisor of Template:Mvar and Template:Mvar is likewise a common divisor of the remainder Template:Math. The analogous equation for the left divisors would be

<math>\rho_0 = \alpha - \beta\psi_0 = \delta(\xi - \eta\psi_0).</math>

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 Template:Math (formally, its Euclidean function or "norm") must be strictly smaller than Template:Mvar, and there must be only a finite number of possible sizes for Template:Math, so that the algorithm is guaranteed to terminate.<ref name="entgtrg">Template:Cite book</ref>

Many results for the GCD carry over to noncommutative numbers. For example, Bézout's identity states that the right Template:Math can be expressed as a linear combination of Template:Mvar and Template:Mvar.<ref>Template:Cite book</ref> In other words, there are numbers Template:Mvar and Template:Mvar such that

<math>\Gamma_\text{right} = \sigma\alpha + \tau\beta.</math>

The analogous identity for the left GCD is nearly the same:

<math>\Gamma_\text{left} = \alpha\sigma + \beta\tau.</math>

Bézout's identity can be used to solve Diophantine equations. For instance, one of the standard proofs of Lagrange's four-square theorem, that every positive integer can be represented as a sum of four squares, is based on quaternion GCDs in this way.<ref name="entgtrg"/>

NotesEdit

Template:Reflist

ReferencesEdit

Template:Reflist

BibliographyEdit

External linksEdit

Demonstrations of Euclid's algorithm
{{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web

|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:EuclideanAlgorithm%7CEuclideanAlgorithm.html}} |title = Euclidean Algorithm |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}

Template:Number theoretic algorithms Template:Ancient Greek mathematics Template:Authority control

Euclidean algorithm

Background: greatest common divisorEdit

ProcedureEdit

Proof of validityEdit

Worked exampleEdit

VisualizationEdit

Euclidean divisionEdit

ImplementationsEdit

Method of least absolute remaindersEdit

Historical developmentEdit

Mathematical applicationsEdit

Bézout's identityEdit

Principal ideals and related problemsEdit

Extended Euclidean algorithmEdit

Matrix methodEdit

Euclid's lemma and unique factorizationEdit

Linear Diophantine equationsEdit

Multiplicative inverses and the RSA algorithmEdit

Chinese remainder theoremEdit

Stern–Brocot treeEdit

Continued fractionsEdit

Factorization algorithmsEdit

Algorithmic efficiencyEdit

Number of stepsEdit

Worst-caseEdit

AverageEdit

Computational expense per stepEdit

Alternative methodsEdit

GeneralizationsEdit

Rational and real numbersEdit

PolynomialsEdit

Gaussian integersEdit

Euclidean domainsEdit

Unique factorization of quadratic integersEdit

Noncommutative ringsEdit

See alsoEdit

NotesEdit

ReferencesEdit

BibliographyEdit

External linksEdit