Migration complete - please let us know if anything isn't working.

# least common multiple

The least common multiple of two (or more) nonzero integers is the least positive integer divisible by all of them. This is usually denoted lcm. For example, lcm(-12,30)=60. Notice

- gcd(
*a*,*b*)^{.}lcm(*a*,*b*) =*ab*, and - lcm(
*a*,*b*) =*ab*if and only if*a*and*b*are relatively prime.

Note that we can use the first of these, and the Euclidean algorithm, to find the least common multiple without
factoring. However, if we know the prime factorization of *a* is
,
and that of *b* is
, then lcm(*a*,*b*) is
.

We can generalize gcd(*a*,*b*)^{.}lcm(*a*,*b*) =
*ab* to three variables in a number of ways:

- gcd(
a,b,c)^{.}lcm(ab,ac,bc) =abc- lcm(
a,b,c)^{.}gcd(ab,ac,bc) =abc- gcd(lcm(
a,b),lcm(a,c),lcm(b,c)) = lcm(gcd(a,b), gcd(a,c),gcd(b,c))

Finally, as a direct result of the properties of min and max functions we have the dual relations:

- gcd(
a, lcm(b,c)) = lcm(gcd(a,b),gcd(a,c))- lcm(
a, gcd(b,c)) = gcd(lcm(a,b),lcm(a,c))

**See Also:** GCD

Printed from the PrimePages <t5k.org> © Reginald McLean.