GCD
   

   

 Math Help -> Number Theory -> Prime -> GCD - Greatest Common Divisor 

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 =  23 × 31 × 50
180 =  22 × 32 × 51
54 =  21 × 33 × 50

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

24 =  23 × 31 × 50
180 =  22 × 32 × 51
54 =  21 × 33 × 50
Minimum   21 × 31 × 50

The smallest exponent of each prime number gives 21 31 50 = 6.  Here is the table, completely filled out.

24 =  23 × 31 × 50
180 =  22 × 32 × 51
54 =  21 × 33 × 50
Minimum (GCD) 6 =  21 × 31 × 50

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 21 31 50 = 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 the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]