Finding the Greatest Common Factor of Two Different Numbers

Date: 01/06/98 at 22:30:01
From: Jared Knight
Subject: GCF using factoring tree

Help! I understand finding factors of whole numbers using a factoring 
tree. Is there a shortcut for finding the greatest common factor of 2 
different numbers after doing so?

Date: 03/10/98 at 12:46:33
From: Doctor Sonya
Subject: Re: GCF using factoring tree

Dear Jared,

You say you can find the factors of a number using factoring trees. 
Very good. That's the first thing you need to know how to do. Now we 
want to use the factoring trees to find the GCF. You're right, there 
is a shortcut. I'm not going to tell you what it is, but I will give 
you some things to think about.

Before doing any hard math thinking (which we're about to do), we need 
to be absolutely clear on our terms. So what is a GCF? The greatest 
common factor of two numbers is the largest whole number that will 
divide evenly into both of them. Do you agree with that definition?

You already know that finding the GCF has something to do with 
factoring trees, so let's think about what the GCF of two numbers has 
to do with their factors. I'll give an example to make things clearer.  
Let's say that our two numbers are 18 and 24, and we want to find the 
GCF. From a factor tree, we know that:
   
                  18 = 2 x 3 x 3
                  24 = 2 x 2 x 2 x 3

Now, every factor of 18 has to be some combination of up to one 2 and 
two 3s. So we have as our factors:

               2 
               3
               2 x 3 = 6
               3 x 3 = 9  etc.

For a number to be the GCF of 18 and 24, it must be a factor of 18, 
right? If it's not, then there's no way it can be a greatest common 
factor of 18 and something else.

If our GCF is a factor if 18, then it must be made up of some 
combination of 2s and 3s (with at most one 2 and at most two 3s). Do 
you see why?

Now, our GCF also has to be a factor of 24, so what does that mean 
about the numbers that make it up? Right, it has to be some 
combination of 2's and 3's, with no more than three 2's and no more 
than one 3. (Remember the factors of 24.) 

Let's summarize what we've done so far. We're looking for the GCF of 
18 and 24. We know from our factor tree that:
 
            18 = 2 x 3 x 3
            24 = 2 x 2 x 2 x 3.

We also know certain things about the factors of the GCF itself. 
Because we factored the 18, we know it is made up of 2's and 3's, and 
it can have no more than one 2 and no more than two 3s. Because we 
factored the 24, we know that it is made up of 2s and 3s, with no more 
than three 2's and one 3. When we put this all together, what do we 
have?

Well, our GCF must have only 2's and 3's as its factors.  That's a 
start. We also know that it can have no more than one 2 as a factor 
(from the 18). It can have no more than one 3 (from the 24). So our 
choices for GCF are limited to:

        2 (one 2, no 3s)
        3 (no 2's, one 3)
        2 x 3 = 6 (one 2, one 3)

        6, the biggest one, is the greatest common factor.

Whew! That was pretty long. Now, I haven't given you all the rules for 
finding the GCF, but try the method we just went through with several 
other pairs of numbers, and see how it works.  I bet you'll be able to 
figure out the pattern.

Good luck.  

-Doctor Sonya, The Math Forum
 http://mathforum.org/dr.math/