Number Theory/Unique Factorization and Multiplicative Functions

The Euclidean Algorithm

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

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 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 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. The Fundamental Theorem of Arithmetic asserts that each integer has a unique prime number decomposition.