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 hence gcd(a, b) ≤ gcd(b, r).The reverse is also true because every divisor of b and r also divides a.
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
For every pair of whole numbers a and b there are two integers s and t such that
2322×20 + 654×(-71) = 6.
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.
Note that any linear combination
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.
- 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
- 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
- Farey series
- Pick's Theorem
- Fermat's Little Theorem
- Wilson's Theorem
- Euler's Function
- Divisibility Criteria
- Equivalence relations
- A real life story
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny