Jamaica Finance

Nov 30 2017

Euclid s Algorithm #factoring #algorithm


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:

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.

    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:


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


    2322 20 + 654 (-71) = 6.


    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.


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


    Related material
    Read more.

  • Written by admin

    Leave a Reply

    Your email address will not be published. Required fields are marked *