- #1

- 198

- 10

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- B
- Thread starter awholenumber
- Start date

- #1

- 198

- 10

- #2

FactChecker

Science Advisor

Gold Member

- 6,636

- 2,684

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

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

- #5

- 198

- 10

Ok , Thanks

- #6

- 474

- 66

- #7

FactChecker

Science Advisor

Gold Member

- 6,636

- 2,684

- #8

- 198

- 10

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

mfb

Mentor

- 35,714

- 12,293

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

It doesn't have a method like this LCM(a, b)=a*b/GCD(a, b) mentioned in it .

- #11

- 19,126

- 10,674

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

- #13

- 19,126

- 10,674

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

- #14

- 198

- 10

- #15

- 10

- 7

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

- 10

- 7

$$

\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

- 10

- 7

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

- #18

mfb

Mentor

- 35,714

- 12,293

Yes, that has been mentioned in post 6 for example.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.

This thread is from 2017, by the way.

Share: