audio read-through Finding the Greatest Common Factor of 2 or 3 Numbers

Example

Question: Find the greatest common factor of $\,27\,$ and $\,18\,.$
Answer: $\,9$

The idea:

The factors of $\,27\,$ are: $\,1\,$   $\,3\,$   $\,9\,$   $\,27$
The factors of $\,18\,$ are: $\,1\,$ $\,2\,$ $\,3\,$ $\,6\,$ $\,9\,$ $\,18\,$  

The common factors of $\,27\,$ and $\,18\,$ (the numbers that appear in both lists) are $\,1\,$, $\,3\,$, and $\,9\,.$

The greatest common factor (the greatest number in the list of common factors) is $\,9\,.$

Efficient Algorithm for Finding the Greatest Common Factor

Here's an efficient algorithm for finding the greatest common factor, when there aren't too many numbers, and they aren't too big.

The process is illustrated by finding the greatest common factor of $\,18\,$, $\,36\,$, and $\,90\,$:

finding the gcf

Why Does This Method Work?

Think about why this method works. As you walk through each step of this discussion, keep comparing with the chart above.

Look at the prime factorizations of each number:

$$ \begin{align} 18 &= 2\cdot3\cdot 3\cr 36 &= 2\cdot 2\cdot 3\cdot 3\cr 90 &= 2\cdot3\cdot 3\cdot 5 \end{align} $$

The number $\,2\,$ goes into each evenly, so separate it off:

$$ \begin{alignat}{2} 18 &= 2\cdot (3\cdot 3)\hphantom{\cdot 3} &&= 2\cdot 9\cr 36 &= 2\cdot (2\cdot 3\cdot 3) &&= 2\cdot 18\cr 90 &= 2\cdot (3\cdot 3\cdot 5) &&= 2\cdot 45 \end{alignat} $$

The number $\,3\,$ goes into each remaining part evenly, so separate it off:

$$ \begin{alignat}{2} 18 &= (2\cdot 3) \cdot (3) \hphantom{\cdot 3} &&= (2\cdot 3)\cdot 3\cr 36 &= (2\cdot 3) \cdot (2\cdot 3) &&= (2\cdot 3)\cdot 6\cr 90 &= (2\cdot 3) \cdot (3\cdot 5) &&= (2\cdot 3)\cdot 15 \end{alignat} $$

Here's the final step:

$$ \begin{align} 18 &= (2\cdot 3\cdot 3)\cdot 1\cr 36 &= (2\cdot 3\cdot 3)\cdot 2\cr 90 &= (2\cdot 3\cdot 3)\cdot 5 \end{align} $$

Other Ways to Apply the Algorithm

Here are some other ways the algorithm might be applied. Of course, you get the same answer any correct way that you do it!

finding the gcf

finding the gcf

finding the gcf

You can also zip over to wolframalpha.com and type in   gcd(18,36,90).  The ‘gcd’ stands for greatest common divisor, which is another name for greatest common factor.

Practice