Euclid's Algorithm

Euclid's Algorithm appears as the solution to the Proposition VII.2 in the Elements:

Given two numbers not prime to one another, to find their greatest common measure.

What Euclid called "common measure" is termed nowadays a common factor or a common divisor. Euclid VII.2 then offers an algorithm for finding the greatest common divisor (gcd) of two integers. Not surprisingly, the algorithm bears Euclid's name.

The algorithm is based on the following two observations:

1. If b|a then gcd(a, b) = b.

   This is indeed so because no number (b, in particular) may have a divisor greater than the number itself (I am talking here of non-negative integers.)

2. If a = bt + r, for integers t and r, then gcd(a, b) = gcd(b, r).

   Indeed, every common divisor of a and b also divides r. Thus gcd(a, b) divides r. But, of course, gcd(a, b)|b. Therefore, gcd(a, b) is a common divisor of b and r and hence gcd(a, b) ≤ gcd(b, r). The reverse is also true because every divisor of b and r also divides a.

Example

Let a = 2322, b = 654.

	2322 = 654·3 + 360		gcd(2322, 654) = gcd(654, 360)
	654 = 360·1 + 294		gcd(654, 360) = gcd(360, 294)
	360 = 294·1 + 66		gcd(360, 294) = gcd(294, 66)
	294 = 66·4 + 30		gcd(294, 66) = gcd(66, 30)
	66 = 30·2 + 6		gcd(66, 30) = gcd(30, 6)
	30 = 6·5		gcd(30, 6) = 6

Therefore, gcd(2322,654) = 6.

For any pair a and b, the algorithm is bound to terminate since every new step generates a similar problem (that of finding gcd) for a pair of smaller integers. Let Eulen(a, b) denote the length of the Euclidean algorithm for a pair a, b. Eulen(2322, 654) = 6, Eulen(30, 6) = 1. I'll use this notation in the proof of the following very important consequence of the algorithm:

Corollary

For every pair of whole numbers a and b there are two integers s and t such that as + bt = gcd(a, b).

Example

2322×20 + 654×(-71) = 6.

Proof

Let a > b. The proof is by induction on Eulen(a, b). If Eulen(a, b) = 1, i.e., if b|a, then a = bu for an integer u. Hence, a + (1 - u)b = b = gcd(a, b). We can take s = 1 and t = 1 - u.

Assume the Corollary has been established for all pairs of numbers for which Eulen is less than n. Let Eulen(a, b) = n. Apply one step of the algorithm: a = bu + r. Eulen(b, r) = n - 1. By the inductive assumption, there exist x and y such that bx + ry = gcd(b,r) = gcd(a,b). Express r as r = a - bu. Hence, ry = ay - buy; bx + (ay - buy) = gcd(a, b). Finally, b(x - uy) + ay = gcd(a, b) and we can take s = x - uy and t = y.

There is also a simple proof that employs the Pigeonhole Principle.

Remark

Note that any linear combination as + bt is divisible by any common factor of a and b. In particular, any common factor of a and b also divides gcd(a, b). In a "reverse" application, any linear combination as + bt is divisible by gcd(a, b). From here it follows that gcd(a, b) is the least positive integer representable in the form as + bt. All the rest are multiples of gcd(a, b). The generalization of the Corollary to what is known as Principal ideal domain is known as Bézout's identity or Bézout's Lemma after the French mathematician Éttiene Bézout (1730-1783), so it often happens that the result stated in the Corollary is also often referred to as Bézout's identity or Bézout's Lemma.

For coprime numbers we get existence of s and t such that as + bt = 1. This Corollary is a powerful tool. It appeared in the 3 Glass and Hour Glass problems. For example, let's prove the Euclid's Proposition VII.30

If two numbers, multiplied by one another make some number, and any prime number measures the product, then it also measures one of the original numbers.

Let a prime p divide the product ab. Assume pa. Then gcd(a, p) = 1. By Corollary, ax + py = 1 for some x and y. Multiply by b: abx + pby = b. Now, p|ab and p|pb. Hence, p|b.

Actually, this proves a generalization of the Proposition VII.30 I used several times on these pages:

Let m|ab and gcd(a, m) = 1. Then m|b.

Proposition VII.30 immediately implies the Fundamental Theorem of Arithmetic although Euclid has never stated it explicitly. The first time it was formulated in 1801 by Gauss in his Disquisitiones arithmeticae.

Fundamental Theorem of Arithmetic

Any integer N can be represented as a product of primes. Such a representation is unique up to the order of prime factors.

Since, by definition, a number is composite if it has factors other than 1 and itself, and these factors are bound to be smaller than the number, we can keep extracting the factors until only prime factors remain. This shows existence of the representation: N = pqr ..., where all p, q, r,... are prime. To prove uniqueness, assume there are two representations: N = pqr ... = uvw.... We see that p divides uvw... By Corollary, it divides one of the factors u, v, w, ... Cancel them out. We can go on chipping away on the factors left and right until no factors remain.

Representation of a number as the product of primes is called prime number decomposition or prime factorization. The Fundamental Theorem of Arithmetic asserts that each integer has a unique prime number decomposition.

Note: Euclid's Algorithm is not the only way to determine the greatest common factor of two integers. If you can find the prime factorizations of the two numbers you can easily determine their gcd as the intersection of the multisets formed by their prime factors. Factor Trees offer a convenient bookkeeping for finding prime factorizations of integers.

References

1. H. Davenport, The Higher Arithmetic, Harper&Brothers, NY
2. R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
3. Oystein Ore, Number Theory and Its History, Dover Publications, 1976
4. S. K. Stein, Mathematics: The Man-Made Universe, 3rd edition, Dover, 2000.

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Algorithm (An Interactive Illustration)
  • Euclid's Game
  • Extension of Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Lame's Theorem - First Application of Fibonacci Numbers
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
• Examples
• Equivalence relations
• A real life story

Related material Read more...
	Factoring with the Factor Tree
	GCD and LCM via Factor Tree
	GCD and LCM by Plain Factorization
	Common Multiples and the Least Common Multiple
	GCD(M, N) x LCM(M, N) = M x N
	Divisibility Criteria
	Euclid's Algorithm
	Algorithm for Computing the LCM
	Factors And Multiples
	Two Properties of Greatest Common Divisor
	Properties of GCD and LCM
	A Line in a Square Grid
	Number of Factors of an Integer
	Extension of Euclid's Game

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny