A question about Greatest common factor (GCF) ?

[awholenumber]

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

 

[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.

 

[awholenumber]

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

 

[FactChecker]

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

Yes.

 

[awholenumber]

Ok , Thanks

 

[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).

 

[FactChecker]

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

 

[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 ?

 

[mfb]

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.

 

[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 .

 

[PeroK]

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 .

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

 

[awholenumber]

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

 

[PeroK]

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

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$

 

[awholenumber]

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

 

[Michael Hardy]

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.

But you don't need to know anything about prime factorizations to find the GCD; you can use Euclid's algorithm, which is very efficient.

 

[Michael Hardy]

You don't need prime factorizations to find GCDs. There is an efficient method not requiring any knowledge of prime numbers: Euclid's algorithm. This is the oldest algorithm still in standard use, dating back to Euclid's writings in the 3rd century BC, and it is very efficient.
$$
\begin{align*}
\gcd(1989,867) & = \gcd(255,867) & & \text{since 255 is the remainder} \\
& & & \text{when 1989 is divided by 867} \\[10pt]
& = \gcd(255,102) & & \text{since 102 is the remainder} \\
& & & \text{when 867 is divided by 255} \\[10pt]
& = \gcd(51,102) & & \text{since 51 is the remainder} \\
& & & \text{when 255 is divided by 102} \\[10pt]
& = \gcd(51,0) & & \text{since 0 is the remainder} \\
& & & \text{when 102 is divided by 51} \\[10pt]
& = 51.
\end{align*}
$$
Thus we have $\dfrac{1989}{867} = \dfrac{51\times39}{51\times17} = \dfrac{39}{17}.$

 

[Michael Hardy]

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.

This is wrong. Euclid's very efficient algorithm for finding GCDs does not require doing anything at all with prime numbers.

 

[mfb]

But you don't need to know anything about prime factorizations to find the GCD; you can use Euclid's algorithm, which is very efficient.

Yes, that has been mentioned in post 6 for example.

This thread is from 2017, by the way.