Three Ways to Find the Greatest Common Factor

Last time, we looked at simplifying a fraction, and the GCF (Greatest Common Factor, also called GCD for Greatest Common Divisor, or HCF for Highest Common Factor) came up. At the end I referred to a source for information about the Euclidean Algorithm for calculating it, and it seems fitting here to look at that and several other methods.

Listing all factors

We can start with this introductory question, from 2005:

Explaining Greatest Common Factor

I am trying to understand what GCF is but I just can not get it.  It is so hard to understand.  I think it has something to do with multiplication.  Please help me.

Doctor Ian answered:

Often when they make up a name like "greatest common factor", you can figure out what it means just by looking at the individual words. 

For example, let's look at two numbers, like 12 and 20.  What are the factors of 12?  Those are the numbers that evenly divide it:

  12 = 1 * 12
     = 2 *  6
     = 3 *  4          Factors: 1, 2, 3, 4, 6, 12

What about the factors of 20?

  20 = 1 * 20
     = 2 * 10
     = 4 *  5          Factors: 1, 2, 4, 5, 10, 20

Do they have any factors in common?  That is, are there any numbers that are factors of both, numbers that appear in both lists?  In fact, there are:

  1, 2, 4

So these are "common factors" of 12 and 20.  So far, so good?

Now, of these three common factors, which is the greatest?  That would be 4, right?  So 4 is the "greatest common factor" of 12 and 20.

Does that make sense?

This is the most basic way to find the GCF of two (or more) numbers, by just following the definition. We list the factors of each number, find those that they have in common, and then chose the largest of these.

Here’s another example, with bigger numbers. Suppose our numbers are 84 and 90. To list the factors of 84, we can just try dividing, in turn by 1, 2, 3, and so on. We find that $$84 = 1\times 84 = 2\times 42 = 3\times 28 = 4\times 21 = 6\times 14 = 7\times 12$$ With experience, you can find quicker ways to do this; for example, when it came to trying 6, I saw that \(6 = 2\times 3\), and I already had \(3\times 28\), so I could pull a 2 off the 28 and tack it onto the 3 to make \(6\times 14\).

Similarly, we find that $$90 = 1\times 90 = 2\times 45 = 3\times 30 = 5\times 18 = 6\times 15 = 9\times 10$$.

So the factors are:$$84: 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84$$ $$90: 1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90$$

Common factors are 1, 2, 3, and 6; so the GCF is 6.

This method is great for small numbers, as well as for understanding what the GCF is. But it’s not the easiest way when the numbers get larger. Even this example wasn’t easy.

Using the prime factorization

To demonstrate the next method, which is useful for middle-sized numbers, here’s a question from 1998:

Finding the Greatest Common Factor of Two Different Numbers

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?

A factor tree is one method for factoring a number as a product of primes. For examples and explanations of this, see this page (and the link near the bottom for more):

Write Numbers as Products of Prime Factors

Doctor Sonya answered, taking it from there:

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?

We have the definition, and we assume we have the prime factors (not a list of all factors, as we did before). Now what?

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?

You might think of putting a little check box above each prime in the list; each set of checks (such as picking the 2 and one of the threes) produces a factor of 18; but if you stick in any primes besides those in the list (e.g. pick 2, 3, and 17), you will not get a factor.

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.

One way to organize this work is to list the prime factors of each number so that they match up, and use only the primes that match: $$\begin{matrix}18 = & 2 & & & \cdot 3 & \cdot 3\\ 24 = & 2 &\cdot 2 & \cdot 2 & \cdot 3 & \\ \text{GCF}= & 2 & & & \cdot 3 & \end{matrix}$$

Another is to write each prime factor with an exponent, and then use the smallest exponent for each prime: $$\begin{matrix}18 = & 2^1 & \cdot 3^2\\ 24 = & 2^3 & \cdot 3^1 \\ \text{GCF}= & 2^1 & \cdot 3^1 & = 6\end{matrix}$$

Let’s try this method with my example, 84 and 90: $$\begin{matrix}84 = & 2 & \cdot 2 & \cdot 3 & & & \cdot 7\\ 90 = & 2 & & \cdot 3 & \cdot 3 & \cdot 5 &\\ \text{GCF}= & 2 & & \cdot 3 & \end{matrix}$$

$$\begin{matrix}84 = & 2^2 & \cdot 3^1 & & \cdot 7^1 \\ 90 = & 2^1 & \cdot 3^2 & \cdot 5^2 \\ \text{GCF}= & 2^1 & \cdot 3^1 & & & = 6\end{matrix}$$

That method is great for middle-sized numbers, when you (a) need to look at prime factors in order to see everything at once, and (b) can find the prime factors without too much trouble.

What if the numbers are too big to factor easily? That’s where the big machinery comes into play.

Euclidean algorithm: introduction

Here’s the question I referred to last time, from 1997:

Euclidean Algorithm

I have this project to do that involves Euclid's theorem (actually it's about the Greatest Common Denominator). Can you tell me what it is in layman's terms, or try to simplify it, please?

Doctor Ezra took this one:

Euclid had a number of theorems, but I suspect that the one you're interested in is also known as the Euclidean Algorithm. This is an algorithm, or procedure, for finding the Greatest Common Divisor (or GCD) of two numbers, and it's based on something with which you are probably familiar.

But first, what's the GCD of two numbers? It's just the largest number that divides both numbers exactly, leaving no remainder. For example, the divisors of 6 are 1, 2, 3 and 6, and the divisors of 15 are 1, 3, 5 and 15, so the GCD of 6 and 15 is the largest number to appear on both lists: 3. In the same way, you can check to see that the GCD of 36 and 210 is 6, and that the GCD of 15 and 8 is 1.

Once again, we start with the definition, which this method will have to satisfy.

Euclid knew that if you divide one number by another, you get a quotient and a remainder, and that the remainder is less than the divisor. For instance, if you divide 7 into 39, it goes 5 times (that's the quotient) with a remainder of 4: 39 = 5*7 + 4. Also, divide 17 into 829: it goes 48 times, with 13 left over: 829 = 816 + 13 = 48*17 + 13.

This can also be stated as: If we divide 829 by 17, the quotient is 48 and the remainder is 13.

So, said Euclid, to find the GCD of two numbers, divide one of them into the other, and I guarantee that the GCD will also exactly divide the remainder. For example,

  210 = 5*36 + 30

the GCD of 210 and 36 is 6, and 6 does divide 30 exactly (30 = 5*6).

Why is this? Well, looking at the equation \(210 = 5\times 36 + 30\), if both 210 and 36 are multiples of 6, then the remainder, \(30 = 210\ – 5\times 36\), is the difference of two multiples of 6, so we could factor out the 6: \(30 = 6(35\ – 5\times 6)\) to show that the remainder, too, is a multiple of 6. This shows that any divisor of the dividend and the divisor (that is, any common divisor) is still a divisor of the remainder. That is, in particular, true of the greatest common divisor.

Now divide the old remainder into the old divisor, and the GCD of the old divisor and the old remainder will exactly divide the new remainder. Keep doing this, said Euclid, until you get a remainder of 0. The last nonzero remainder you get will be the GCD of the two numbers you started with. 

Let's do this with 210 and 36:

  210 = 5*36 + 30  Divisor 36, remainder 30
   36 = 1*30 + 6   Divisor 30, remainder 6
   30 = 5*6  + 0   Divisor  6, remainder 0.

So, 6 is the last nonzero remainder, and that's the GCD of 210 and 36.

Try this out with 21 and 36, with 21 and 34, and with 288 and 178.

The way I like to remember this is, the last divisor is the greatest common divisor.

Euclidean algorithm: example

For an example of how we do it in practice, here’s a question from 1997:

Formula for Greatest Common Divisor

Is there a formula to get the greatest common factor?

Doctor Jerry replied:

I assume you mean the greatest common divisor of integers a and b, the largest integer that divides both of a and b.  It can be calculated using a 2300 year old method called Euclid's algorithm.

I'll explain the algorithm with an example.  Let's find the gcd of 210 and 990.

Divide 990 by 210:  quotient 4, remainder 150; ignore quotient
Divide divisor from previous step by remainder from previous step
   divide 210 by 150: quotient 1, remainder 60; ignore quotient
Divide divisor from previous step by remainder from previous step
   divide 150 by 60: quotient 2, remainder 30; ignore quotient
Divide divisor from previous step by remainder from previous step
   divide 60 by 30: quotient 2, remainder 0.

When the remainder becomes 0, as it always will, then go to the previous step and choose the remainder, in this case 30.  This is the gcd!  Neat!

The step of dividing and ignoring the quotient can be done on many calculators, using the MOD operation.  For example, on my calculator (an HP48G), I enter 990 and 210 and press MOD.  I get 150 on the screen.

The Windows Calculator, similarly, has a “mod” button in Scientific mode. Using that, we just have to enter this:

990 mod 210 = 150

210 mod 150 = 60

150 mod 60 = 30

60 mod 30 = 0

So the last divisor, 30, is the GCF.

Euclidean algorithm: proof

For a deeper look consider this question from 1998:

Explaining the Euclidean Algorithm

There is an algorithm for prime factorization called the Division Algorithm. Given integers s and t, t > 0, there exist unique integers q and r such that s = t*q + r and 0 =< r < t.

We need to find the GCF of both numbers. For example, to find the GCF of 54 and 198 by the division algorithm, divide 198 by 54. Repeat the process using the divisor as the new dividend and the remainder as the new divisor:

   198 = 3*54 + 36
    54 = 1*36 + 18
    36 = 2*18 + 0

When we get 0 as the remainder, the last divisor, here 18, is the GCF of the given integers. The procedure is called the Euclidean algorithm. I need to know why this algorithm works. What is the explanation for why these particular steps give you the GCF of the two numbers?

Doctor Rob explained:

At each step, you can show that if d divides the divisor t and the dividend s, it also divides the remainder r. If d divides t, write t = d*T. If d divides s, write s = d*S. Then using the equation:

   r = s - q*t
   r = d*S - q*d*T
   r = d*(S - q*T)
   r = d*R

and so d divides r, too.

This is the formal version of what I demonstrated with a mere example above.

This shows that any common divisor of the first two numbers must also divide the last divisor, by working down the chain of equations one at a time. (You can use the Principle of Mathematical Induction on the number of steps to make this into a proof.)

Similarly, if d divides the divisor t and the remainder r, it also divides the dividend s. Write t = d*T, r = d*R. Then:

   s = q*t + r
   s = q*d*T + d*R
   s = d*(q*T + R)
   s = d*S

and so d divides s, too.

This shows that any factor of the last divisor, including that last divisor itself, also divides both of the first numbers, by working up the chain of equations one step at a time. (You can make this into a proof using the Principle of Mathematical Induction, too.)

Put these two parts together to conclude that the greatest common divisor of the two numbers equals the last divisor in the Euclidean Algorithm.

It was necessary to go both ways in order to show that each step neither loses common factors, nor introduces new common factors. As a result, the GCF is preserved through the entire process, and the last divisor (which is found to divide the previous one exactly) must be the greatest common divisor of the original pair.

For a little of the history of the method, see:

The Official Euclidean Algorithm

For yet another method (Knuth), see:

Greatest Common Factor

And if you want to take it a step further, read:

Using Euclid's Algorithm with Three Numbers

Putting together all that we’ve seen, we have three main ways to find a GCF:

• For numbers small enough to easily list all the factors of each, just do so and take the largest one in both lists. (Or just look at the numbers and recognize the GCF, as in a case like 6 and 18, where it is “obvious” that 6 itself is the GCF.)
• For numbers where that would be difficult, but you can still make a factor tree and write out the prime factorization, do so and pick out the smallest power of each prime, in either of the numbers. If a prime does not appear in both numbers, then its exponent is 0, and you can ignore it.
• For numbers you don’t want to factor, use the Euclidean algorithm. It can be more work than the other methods for some small numbers, but works great for big ones.