Section 1.3: GCDs and Factorization

1.3 GCDs and Factorization

Here's a computation we saw earlier:
Your browser does not support java.
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:
Your browser does not support java.
From the output we see that
272 = 2⁴ · 17¹.

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.
Your browser does not support java.
The output tells us that
a = 7920 = 2⁴ · 3² · 5¹ · 11¹
and
b = 4536 = 2³ · 3 ⁴ · 7¹.
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 = 2^m · 3ⁿ.
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
2³ · 3² = 72.
In general, suppose we have the prime-power factorizations
a =
and
b =
Note: It is possible that some of the m₁, . . . , m_k and n₁, . . . , n_k 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:
Your browser does not support java.
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 5³ 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 7² 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) = 5³ · 7² = 6125.
The Java applet below will compute greatest common divisors. We can use it to check our computation:
Your browser does not support java.
Looks good.

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:
Your browser does not support java.
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