Euclid's Algorithm
Euclid's algorithm appears as the solution to the Proposition VII.2 in the Element's:
|
Given two numbers not prime to one another, to find their greatest common measure.
|
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 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 exist 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 an arbitrary field 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 p a. 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. The Fundamental Theorem of Arithmetic asserts that each integer has a unique prime number decomposition.
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.
Copyright © 1996-2009 Alexander Bogomolny
|
