# B 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

Gold Member
2018 Award
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

Gold Member
2018 Award
Ok , so the same prime factorization is used to find the LCM too , right ?
Yes.

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

Gold Member
2018 Award
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

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.

#### 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

Homework Helper
Gold Member
2018 Award
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

Homework Helper
Gold Member
2018 Award
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$

mfb

#### 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

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

"A question about Greatest common factor (GCF) ?"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving