Question

How do I find the (LCM) or the (LCD) of fraction?

How do I find the (LCM) or the (LCD) of fraction?

Is the LCM the same as the LCD?

Do they have a link with each other?

Answer 1

Yet another way, which I mentioned to a number of students, is by first finding the GCD (greatest common divisor) and using the fact that LCM(x,y) * GCD(x,y) = xy.

The GCD can be found by Euclid's algorithm which proceeds by successively subtracting multiples of the smaller argument from the larger one. The base case is GCD(n,0) = GCD(0,n) = n. For large arguments, this is the fastest method possible.

Example:

x = 632, y = 412

GCD(632,412) = GCD(220,412) since 632 - 412 = 220.

= GCD(220,192) since 412 - 220 = 192.

= GCD(28,192) since 220 - 192 = 28.

= GCD(28,24) since 192 - 6*28 = 24.

= GCD(4,24) since 28 - 24 = 4.

= GCD(4,0) since 24 - 6*4 = 0

= 4 using the base case.

Now for the LCM:

LCM(632,412) = 632*412 / GCD(632,412) = 632*412/4 = 65096.

The nice thing about this method is that you don't need prime factorizations of the two numbers, which are very hard to find if the numbers are very large with very large prime factors.