A question about Greatest common factor (GCF) ?

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

:nb)
 

Answers and Replies

  • #2
FactChecker
Science Advisor
Gold Member
6,636
2,684
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
198
10
Ok , so the same prime factorization is used to find the LCM too , right ?
 
  • #4
FactChecker
Science Advisor
Gold Member
6,636
2,684
Ok , so the same prime factorization is used to find the LCM too , right ?
Yes.
 
  • #6
474
66
I dare to disagree, Euclid's algorithm or binary GCD are used to find GCD, then LCM(a, b)=a*b/GCD(a, b).
 
  • Like
Likes FactChecker
  • #7
FactChecker
Science Advisor
Gold Member
6,636
2,684
I stand corrected. I was not familiar with these algorithms. The binary GCD algorithm and Euclidean_algorithm are interesting.
 
  • #8
198
10
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
35,714
12,293
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
198
10
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,126
10,674
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!
 
  • #12
198
10
lol ok , first let me somehow finish this one book properly :wink:
 
  • #13
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,126
10,674
lol ok , first let me somehow finish this one book properly :wink:

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
198
10
Thanks for sharing , i will keep this in my mind and maybe someday i will be able to use this advanced method . :nb)
 
  • #15
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.
 
  • #16
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}.##
 
  • #17
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.
 
  • #18
35,714
12,293
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.
 

Related Threads on A question about Greatest common factor (GCF) ?

Replies
4
Views
829
Replies
1
Views
844
  • Last Post
Replies
11
Views
5K
  • Last Post
Replies
1
Views
3K
Replies
2
Views
12K
Replies
1
Views
2K
Replies
2
Views
697
Replies
3
Views
408
Replies
7
Views
722
  • Last Post
Replies
2
Views
2K
Top