Here's a computation we saw earlier:

On the basis of the output, we see that gcd(223092870, 6227020800) = 30030.

Given two integers

aandb, another way to compute gcd(a,b) is to look at the factorizations ofaandb. The applet below computes factorizations of integers. For example, here is the factorization ofn= 272:From the output we see that

272 = 2 ^{4}· 17^{1}.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 andb= 4536.The output tells us that

a= 7920 = 2^{4}· 3^{2}· 5^{1}· 11^{1}and

b= 4536 = 2^{3}· 3^{4}· 7^{1}.Now if

ddivides bothaandb, then all of the prime divisors ofdhave to divideaand all of the prime divisors ofdhave to divideb. The only primes that divide bothaandbare 2 and 3, so any positive common divisor must have the formd= 2^{m}· 3^{n}.What are the largest choices of

mandnwe can take? Well, on the basis of the factorizations,if d|a, thenm4, and ifd|bthenm3.So, we've got to take

m3. Similarly,if d|athenn2, and ifd|bthenn4.This time, we've got to take

n2. Thus, taking the biggest possible values fornandm, we see that the greatest common divisor is2 ^{3}· 3^{2}= 72.In general, suppose we have the prime-power factorizations

a=_{}and

b=_{}

Note:It is possible that some of them_{1}, . . . ,mand_{k}n_{1}, . . . ,nare 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._{k}The greatest common divisor of

aandbisgcd( a,b) =_{}.To see how this works in practice, let's look at another example. Suppose that we have

a= 165620000 andb= 65984625. Here are the factorizations:To compute gcd(

a,b), we just start comparing prime factors. Since 2 is a factor ofabut notb, 2 is not a factor of gcd(a,b). Similarly, since 3 is a factor ofbbut nota, 3 is not a factor of gcd(a,b). Now 5 is a factor of bothaandb, and the smallest exponent on 5 is 3, so 5^{3}is a factor of gcd(a,b). Also, 7 is a factor of bothaandb, where the smallest exponent is 2, so that 7^{2}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 atgcd( a,b) = 5^{3}· 7^{2}= 6125.The Java applet below will compute greatest common divisors. We can use it to check our computation:

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:

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

Copyright © 2001 by W. H. Freeman and Company