# B A question about Greatest common factor (GCF) ?

1. Apr 16, 2017

### awholenumber

When we try to find the Greatest common factor (GCF) of two numbers , does it only involve prime factorization ?

2. Apr 16, 2017

### FactChecker

Yes. The GCF is a product of primes but is not usually a prime itself. Prime factorization of both numbers is the way to find out what the GCF is. If you have the prime factorization of both numbers, it is easy to calculate the GCF.

3. Apr 16, 2017

### awholenumber

Ok , so the same prime factorization is used to find the LCM too , right ?

4. Apr 16, 2017

### FactChecker

Yes.

5. Apr 16, 2017

### awholenumber

Ok , Thanks

6. Apr 16, 2017

### SlowThinker

I dare to disagree, Euclid's algorithm or binary GCD are used to find GCD, then LCM(a, b)=a*b/GCD(a, b).

7. Apr 16, 2017

### FactChecker

I stand corrected. I was not familiar with these algorithms. The binary GCD algorithm and Euclidean_algorithm are interesting.

8. Apr 16, 2017

### awholenumber

Ok, i have one more doubt .
The GCF of two numbers involves prime factorization of those two numbers , then multiply those factors both numbers have in common

Isnt LCM about finding the least common multiple of two numbers ?

What does that have anything to do with prime numbers ?

9. Apr 16, 2017

### Staff: Mentor

You can find the LCM via LCM(a, b)=a*b/GCD(a, b), if you have the GCD first.
That is often the most practical way to find the LCM.

Prime factorization is just one possible way to find the GCD. For large numbers, it can be very time-consuming, and different algorithms can be more efficient.

10. Apr 16, 2017

### awholenumber

Thanks for the information mfb , i am just trying to cover the algebra 1 for dummies book .
It doesn't have a method like this LCM(a, b)=a*b/GCD(a, b) mentioned in it .

11. Apr 16, 2017

### PeroK

You'll find that in an "algebra for intelligent students" textbook!

12. Apr 16, 2017

### awholenumber

lol ok , first let me somehow finish this one book properly

13. Apr 16, 2017

### PeroK

It's still worth understanding why the two are related. The basic argument is:

$a = a'g, b = b'g$

Where $g$ is the GCD of $a$ and $b$ and $a', b'$ are how much bigger $a$ and $b$ are than $g$.

For example: if $a = 42$ and $b = 15$, then $g = 3$ and $a=14 \times 3, b = 5 \times 3$, hence $a' = 14, b' = 5$

Now, the LCM of $a$ and $b$ must have as factors simply $a', b'$ and $g$, so $l = a'b'g = a'b = a'gb/g = ab/g$

You can now see that the LCM is the product of $a$ and $b$, divided by the GCD.

In our example:

$LCM(42, 15) = \frac{42 \times 15}{3} = 210$

14. Apr 16, 2017

### awholenumber

Thanks for sharing , i will keep this in my mind and maybe someday i will be able to use this advanced method .