|
|
|
The Greatest Common Divisor of two or more numbers is the largest number that evenly divides all the numbers.
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.
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.
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.
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!
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.