The Greatest Common Divisor of two or more numbers is the largest number that
evenly divides all the numbers.

**Greatest Common Divisor**

The best way to find Greatest Common Divisor (GCD) is to find the
prime factorization of the operands, and then take the minima of all their
exponents.
I'll illustrate with some examples:

Find the GCD of the following numbers: 24, 180, 54. Their prime
factorizations are:

24 = |
2^{3 } × 3^{1 } × 5^{0} |

180 = |
2^{2 } × 3^{2 } × 5^{1} |

54 = |
2^{1 } × 3^{3 } × 5^{0} |

Now add another row to this table, for the smallest exponent of each
prime number:

24 = |
2^{3 } × 3^{1 } × 5^{0} |

180 = |
2^{2 } × 3^{2 } × 5^{1} |

54 = |
2^{1 } × 3^{3 } × 5^{0} |

Minimum |
2^{1 } × 3^{1 } × 5^{0} |

The smallest exponent of each prime number gives 2^{1 }3^{1 }
5^{0} = 6. Here is the table, completely filled out.

24 = |
2^{3 } × 3^{1 } × 5^{0} |

180 = |
2^{2 } × 3^{2 } × 5^{1} |

54 = |
2^{1 } × 3^{3 } × 5^{0} |

Minimum (GCD) 6 = |
2^{1 } × 3^{1 } × 5^{0} |

Practice this method with a few different sets of numbers, and you will see
how it works.

### Still not clear?

On this page, you see an example of finding the GCD of 24, 180, and 54.
Each of the numbers was decomposed into its prime factorization, showing the
exponent (number of factors) of each of the prime numbers 2, 3, and 5.
Then, to find the GCD, I write down the prime factorization of the GCD which
uses the smallest exponent of each prime number. In this case, the
smallest exponent of 2 is 1, because 54 only has a single factor of 2. The
smallest exponent of 3 is also 1, because 24 has only a single factor of 3. The
smallest exponent of 5 is 0, because neither 24 nor 54 is divisible by 5. So the
GCD is 2^{1} 3^{1} 5^{0} = 6.

### What's Next?

Do you understand how Prime Factorization helps you find the GCD of two or
more numbers? If not, send me an email (click the link, below) and I will
be glad to help you. If so, then the next topic should be a snap for you
-- it's almost exactly the same -- how to find the
Least Common Multiple (LCM) of two or more numbers.

### Internet references

www.faust.fr.bw.schule.de/mhb/ggTeng.htm
-- helps you practice finding the GCD of two numbers in your head. Go
ahead, see how smart you are!

### Related pages in this website

How to do Prime Factorization

More advanced theorems involving GCD,
Euclid's First Theorem, etc.

The webmaster and author of this Math Help site is
Graeme McRae.