Greatest Common Factors, Least Common Multiples

Date: 8/29/96 at 20:35:44
From: Anonymous
Subject: Greatest Common Factors, Explained!

Please explain greatest common factors, how to find them, and how they 
are different from lowest common multiples.

Thank you,
Amber

Date: 8/30/96 at 13:41:11
From: Doctor Tom
Subject: Re: Greatest Common Factors, Explained!

Hi Amber,

The "greatest common factor" is also often called the "greatest common 
divisor", or GCD, and it is the largest number that divides all of the 
numbers in question.

For example, the GCD of 12 and 18 is 6, since 6 divides both numbers 
evenly and nothing larger does.

A couple of other examples:

the GCD of 7 and 17 is 1
the GCD of 7 and 49 is 7
the GCD of 100 and 72 is 4

Here's a method to find the GCD of two numbers, which I will show by 
example.  Apply exactly the same method in your case. I'll find the 
GCD of 12070 and 41820:

  41820 = 3*12070 + 5610
  12070 = 2*5610 + 850
   5610 = 6*850 + 510
    850 = 1*510 + 340
    510 = 1*340 + 170
    340 = 2*170 + 0

As soon as the remainder is 0, you've got the answer: 170.

These are big numbers; usually the number of steps to the GCD is much 
smaller.

If you need to find the GCD of three numbers, A, B, and C, for 
example, let D = GCD(A, B) and your answer will be the GCD of D and C, 
and so on.

The least common multiple is the smallest number that all your numbers 
divide, which is sort of the opposite of the GCD.

-Doctor Tom,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/