Expert: Josh - 1/16/2005

Question
Hello:

What method or methods (calculations) would you recommend using for determining the greatest common factor and of determining  the least common multiple for two numbers or more?

For example, what is the gcf and and lcm for 124, 244, and 612.

I thank you for your reply.

Answer
Hi,

For smaller numbers, intuition works best.
For instance, the factors for 48 are kind of obvious, by inspection, we can very quickly find {1,2,3,4,6,8,12,16,24,48}.

In general, if the factorization is not immediately obvious, use the prime factorization method.

The idea behind prime factorization is that every integer can be decomposed into a product of prime numbers (repeating prime numbers are permitted).

Suppose we want to find all the factors for the number N.
Step 1:
Write down a list of prime numbers in increasing order.
Primes, P={2,3,5,7,11,13,17,...}
Step 2:
Start with the smallest prime number, let's call this p.
IF p divides N, p is a factor. Let N become N/p and repeat step 2.
OTHERWISE, pick the next larger prime number in the list, and try again while p is less than or equal to N.

eg., To factorize N=124, let p=2 to begin with.
Clearly, 2 divides 124. So, we put 2 into the list of factors, F. So far, we have identified one factor F={2}.

Repeating step 2, with N=124/2=62, does 2 divide 62?
Yes, so, we put 2 into the list of factors, F. Now, F={2,2}.
Repeating step 2, with N=62/2=31, does 2 divide 31?
No, so, we work with the next prime number 3.

Does 3 divide 31?
No, so, we pick the next prime number 5.

Does 5 divide 31?
No, so, we pick the next prime number 7.

Does 7 divide 31?
No, so, we pick the next prime number 11.

Does 11 divide 31?
No, so, we pick the next prime number 13.

Does 13 divide 31?
No, so, we pick the next prime number 17.

Does 17 divide 31?
No, so, we pick the next prime number 19.

Does 19 divide 31?
No, so, we pick the next prime number 23.

Does 23 divide 31?
No, so, we pick the next prime number 29.

Does 29 divide 31?
No, and the next prime number is 31 (same as N).
So, we stop here.

The factorization for 124 is therefore
124=2x2x31.

Doing the same for 244,
244=2x122,
  =2x2x61. 61 is actually a prime, so, nothing more to do.

Doing the same for 612,
612=2x306
  =2x2x153
  =2x2x3x51
  =2x2x3x3x17.

Now, the GCF is found by comparing these factorizations. We see what is the largest number they have in common.
In this case, 2x2 is common to all three numbers.
So, the answer is GCF{124,244,612}=4.

The least common multiple is found by adding the smallest combination of prime numbers such that all three factorizations look the same.

124=2x2x31.    ...[#1]
244=2x2x61.    ...[#2]
612=2x2x3x3x17 ...[#2]

For [#1], we need to multiply it by 3x3x17x31x61, since these prime numbers are missing from [#1].
You can do the same with [#2], (but not really necessary)
we need to multiply [#2] by 3x3x17x31 to bring it in line with the others.
Similarly, with [#3], we need to multiply it by 31x61.
So, the smallest common multiple is
2x2x3x3x17x31x61=1157292.

Okay?