Least Common Multiple (LCM)

Least Common Multiple (LCM)

https://en.wikipedia.org/wiki/Least_common_multiple

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by LCM(a, b), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero.

Note : Negative integers and zero aren’t candidates for LCM.

Example

lcm ⁡ (4 , 6)

Multiples of 4 are: 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, . . .
Multiples of 6 are: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, . . .
Common multiples of 4 and 6 are the numbers that are in both lists: 12, 24, 36, 48, 60, 72, . . .
In this list, the smallest number is 12. Hence, the least common multiple is 12.

Applications

When adding, subtracting, or comparing simple fractions, the least common multiple of the denominators (often called the lowest common denominator) is used, because each of the fractions can be expressed as a fraction with this denominator. For example,

2/21 + 1/6 = 4/42 + 7/42 = 11/42

where the denominator 42 was used, because it is the least common multiple of 21 and 6.

Using GCD to calculate LCM

The least common multiple can be computed from the greatest common divisor (gcd) with the formula

lcm(a , b) = | a b | / gcd (a , b)

To return to the example above,

lcm(21 , 6) = 6 × 21 / gcd(21 , 6) = 6 × 21 / 3 = 6 × 7 = 42.