Euclidean algorithm

This article is not about Euclidean geometry.

The Euclidean algorithm (also called Euclid's algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. Its major significance is that it does not require factoring the two integers. It is also significant in that it is one of the oldest algorithms known, dating back to the Greeks. The algorithm works by repeatedly dividing the two numbers and the remainder in turns. The Euclidean algorithm is not restricted to integers; it may be used to compute gcd of elements of any Euclidean domain, for example polynomials over a field.

History of Euclidean Algorithm

The Euclidean algorithm is one of the oldest algorithms known, since it appeared in Euclid's Elements around 300 BC. Euclid originally formulated the problem geometrically, as the problem of finding a common "measure" for two line lengths, and his algorithm proceeded by repeated subtraction of the shorter from the longer segment. However, the algorithm was probably not discovered by Euclid and it may have been known up to 200 years earlier. It was almost certainly known by Eudoxus of Cnidus (about 375 BC); and Aristotle (about 330 BC) hinted at it in his Topics, 158b, 29-35.

Description of the algorithm

Given two natural numbers a and b, check if b is zero. If yes, a is the gcd. If not, repeat the process using b and the remainder after integer division of a by b (written a modulo b below). The algorithm can be naturally expressed using tail recursion such as the following pseudocode:

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

The original algorithm as described by Euclid treated it as a geometric problem, and hence used repeated subtraction of the smaller number from the larger number rather than integer division. This is equivalent to the following pseudocode, which is considerably less efficient than the method explained above:

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

By keeping track of the quotients occurring during the algorithm, one can also determine integers p and q with ap + bq = gcd(a, b). This is known as the extended Euclidean algorithm.

As an example, consider computing the gcd of 1071 and 1029, which is 21, with this algorithm:

a	b	Explanation
1071	1029	Step 1: We start by putting the larger number on the left, and the smaller on the right.
1029	42	Step 2: The remainder of 1071 divided by 1029 is 42, which is put on the right, and the divisor 1029 is put on the left.
42	21	Step 3: We repeat step 2, dividing 1029 by 42, and get 21 as remainder.
21	0	Step 4: Repeat step 2 again, since 42 is divisible by 21, we get 0 as remainder, and the algorithm terminates. The number on the left, that is 21, is the gcd as required.

These algorithms can be used in any context where division with remainder is possible. This includes rings of polynomials over a field as well as the ring of Gaussian integers, and in general all Euclidean domains. Applying the algorithm to the more general case other than natural number will be discussed in more detail later in the article.

Proof of correctness

Suppose a and b are the natural numbers whose gcd has to be determined. And suppose the remainder of the division of a by b is r. Therefore a = qb + r where q is the quotient of the division.

Any common divisor of a and b is also a divisor of r. To see why this is true, consider that r can be written as r = a − qb. Now, if there is a common divisor d of a and b such that a = sd and b = td, then r = (s−qt)d. Since all these numbers, including s−qt, are whole numbers, it can be seen that r is divisible by d.

The above analysis is true for any divisor d; thus, the greatest common divisor of a and b is also the greatest common divisor of b and r. Therefore it is enough if we continue searching for the greatest common divisor with the numbers b and r. Since r is smaller in absolute value than b, we will reach r = 0 after finitely many steps.

Running time

When analyzing the running time of Euclid's algorithm, it turns out that the inputs requiring the most divisions are two successive Fibonacci numbers, and the worst case requires O(n) divisions, where n is the number of digits in the input. However, it must be noted that the divisions themselves are not constant time operations; the actual time complexity of the algorithm is $O(n^{2})$ . The reason is that division of two n-bit numbers takes time $O(n(m+1))$ , where m is the length of the quotient. Consider the computation of gcd(a,b) where a and b have at most n bits, let $a_{0},\dots ,a_{k}$ be the sequence of numbers produced by the algorithm, and let $n_{0},\dots ,n_{k}$ be their lengths. Then $k=O(n)$ , and the running time is bounded by

O{\Big (}\sum _{i<k}n_{i}(n_{i}-n_{i+1}+2){\Big )}\leq O{\Big (}n\sum _{i<k}(n_{i}-n_{i+1}+2){\Big )}\leq O(n(n_{0}+2k))\leq O(n^{2}).

This is considerably better than Euclid's original algorithm, in which the modulus operation is effectively performed using repeated subtraction in $O(2^{n})$ steps. Consequently, that version of the algorithm requires $O(2^{n}n)$ time for n-digit numbers, or $O(m\log {m})$ time for the number m.

Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity. An alternative algorithm, the binary GCD algorithm, exploits the binary representation used by computers to avoid divisions and thereby increase efficiency, although it too is O(n²); it merely shrinks the constant hidden by the big-O notation on many real machines.

Relation with continued fractions

The quotients that appear when the Euclidean algorithm is applied to the inputs a and b are precisely the numbers occurring in the continued fraction representation of a/b. Take for instance the example of a = 1071 and b = 1029 used above. Here is the calculation with highlighted quotients:

1071 = 1029 × 1 + 42

1029 = 42 × 24 + 21

42 = 21 × 2 + 0

From this, one can read off that

{\frac {1071}{1029}}=\mathbf {1} +{\frac {1}{\mathbf {24} +{\frac {1}{\mathbf {2} }}}}

.

This method can even be used for real inputs a and b; if a/b is irrational, then the Euclidean algorithm will not terminate, but the computed sequence of quotients still represents the (now infinite) continued fraction representation of a/b.

Generalisation to Euclidean domains

The Euclidean algorithm can be applied to some rings, not just the integers. The most general context in which the algorithm terminates with the greatest common divisor is the so-called Euclidean domain. These include the Gaussian integers and polynomial rings over a field.

As an example, consider the ring of polynomials with rational coefficients. In this ring, division with remainder is carried out using long division, also known as synthetic division. The resulting polynomials are then made monic by factoring out the leading coefficient.

We calculate the greatest common divisor of

x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)

and

x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2)

Following the algorithm gives these values:

a	b
$x^{4}-4x^{3}+4x^{2}-3x+14$	$x^{4}+8x^{3}+12x^{2}+17x+6$
$x^{3}+{\frac {2}{3}}x^{2}+{\frac {5}{3}}x-{\frac {2}{3}}$	$x^{4}-4x^{3}+4x^{2}-3x+14$
$x^{2}+x+2$	$x^{3}+{\frac {2}{3}}x^{2}+{\frac {5}{3}}x-{\frac {2}{3}}$
$0$	$x^{2}+x+2$

This agrees with the explicit factorization. For general Euclidean domains, the proof of correctness is by induction on some size function. For the integers, this size function is just the identity. For rings of polynomials over a field, it is the degree of the polynomial (note that each step in the above table reduces the degree by one).

C/C++/Java implementation

int gcd(int a, int b) {
  if (b == 0)
    return a;

  return gcd(b, a % b);
}

This can be rewritten iteratively as:

int gcd(int a, int b) {
  int t;
  while (b != 0) {
    t = b;
    b = a % b;
    a = t;
  }
  return a;
}

References

Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Sections 4.5.2–4.5.3, pp.333–379.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 31.2: Greatest common divisor, pp.856–862.

External links