Here's a computation we saw earlier:
On the basis of the output, we see that gcd(223092870, 6227020800) = 30030.
Given two integers a and b, another way to compute gcd(a, b) is to look at the factorizations of a and b. The applet below computes factorizations of integers. For example, here is the factorization of n = 272:
From the output we see that
272 = 24 · 171.
When computing gcds, it will be handy to be able to easily compute the factorization of two integers. The applet below allows us to do just that. To illustrate, let's take a = 7920 and b = 4536.
The output tells us that
a = 7920 = 24 · 32 · 51 · 111
b = 4536 = 23 · 3 4 · 71.
Now if d divides both a and b, then all of the prime divisors of d have to divide a and all of the prime divisors of d have to divide b. The only primes that divide both a and b are 2 and 3, so any positive common divisor must have the form
d = 2m · 3n.
What are the largest choices of m and n we can take? Well, on the basis of the factorizations,
if d | a, then m 4, and if d | b then m 3.
So, we've got to take m 3. Similarly,
if d | a then n 2, and if d | b then n 4.
This time, we've got to take n 2. Thus, taking the biggest possible values for n and m, we see that the greatest common divisor is
23 · 32 = 72.
In general, suppose we have the prime-power factorizations
Note: It is possible that some of the m1, . . . , mk and n1, . . . , nk are equal to 0. Writing two integers as products of prime powers over the same set of primes is a useful trick when writing proofs involving prime-power factorizations. You can use it yourself, as long as you advise the reader of what you are doing.
The greatest common divisor of a and b is
gcd(a, b) = .
To see how this works in practice, let's look at another example. Suppose that we have a = 165620000 and b = 65984625. Here are the factorizations:
To compute gcd(a, b), we just start comparing prime factors. Since 2 is a factor of a but not b, 2 is not a factor of gcd(a, b). Similarly, since 3 is a factor of b but not a, 3 is not a factor of gcd(a, b). Now 5 is a factor of both a and b, and the smallest exponent on 5 is 3, so 53 is a factor of gcd(a, b). Also, 7 is a factor of both a and b, where the smallest exponent is 2, so that 72 is a factor of gcd(a, b). The factors 13 and 19 are eliminated in the same manner as 2 and 3, and we arrive at
gcd(a, b) = 53 · 72 = 6125.
The Java applet below will compute greatest common divisors. We can use it to check our computation:
If you play around with the gcd applet, you will find that it computes gcds very quickly, even for huge numbers. In fact, we can use it on numbers that are too large for us to factor:
How does it find gcds without factoring the numbers? We will learn the secret in the next chapter.
Section 1.1 | Section 1.2 | Section 1.3 | Section 1.4 | Section 1.5
Chapter 1 | DNT Table of Contents
Copyright © 2001 by W. H. Freeman and Company