# 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:

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

- 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 hencegcd(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

## Corollary

For every pair of whole numbers a and b there are two integers s and t such that

### Example

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

## Proof

Let a > b. The proof is by induction on Eulen(a, b). If

Assume the Corollary has been established for all pairs of numbers for which Eulen is less than n. Let

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

## Remark

Note that any linear combination *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

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

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:

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

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

- Modular Arithmetic
- Chinese Remainder Theorem
- Euclid's Algorithm
- Pick's Theorem
- Fermat's Little Theorem
- Wilson's Theorem
- Euler's Function
- Divisibility Criteria
- Examples
- Equivalence relations
- A real life story

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

Copyright © 1996-2018 Alexander Bogomolny

71685671