This article page is a stub, please help by expanding it.
The least common multiple (LCM or lcm) of one or more nonzero integers is the smallest positive integer that is a multiple of all those numbers. For example, the LCM of 12 and 14 is 84; no smaller multiple of 12 is also divisible by 14, nor is any smaller multiple of 14 also divisible by 12.
GCD and LCM in terms of the prime factorization
From the prime factorization of
![{\displaystyle m_{i}=\prod _{j=1}^{\pi (\max(m_{1},\ldots ,m_{n}))}{p_{j}}^{\alpha _{j}(i)},\quad 1\,\leq \,i\,\leq \,n,\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/86b5756c0d18c899ac8cae47c87906a6ddc6bf0b)
where
is the number of primes up to
, and
is the
th prime number, we have
![{\displaystyle \gcd(m_{1},\ldots ,m_{n})=\prod _{j=1}^{\pi (\max(m_{1},\ldots ,m_{n}))}{p_{j}}^{\min(\alpha _{j}(1),\ldots ,\alpha _{j}(n))}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/5afd647de908e485d4a4df0d5ac7a61970da43c3)
and
![{\displaystyle {\rm {lcm}}(m_{1},\ldots ,m_{n})=\prod _{j=1}^{\pi (\max(m_{1},\ldots ,m_{n}))}{p_{j}}^{\max(\alpha _{j}(1),\ldots ,\alpha _{j}(n))}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/790f857f5a5a9f6cb11cc3d762b275366c009771)
Formulae
Formulae relating LCM to GCD
Since
![{\displaystyle m+n={\rm {max}}(m,n)\,+\,{\rm {min}}(m,n),\quad m\leq n,\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/9125976bdf18d9f58d81dcf1da4773b643647413)
then the least common multiple (LCM) of two nonzero integers
and
is related to their greatest common divisor (GCD) by
![{\displaystyle |mn|={\rm {lcm}}(m,n)\cdot \gcd(m,n),\quad mn\neq 0,\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/27433a76e210e075cbee15ed16edb40e5cdc5ef0)
where the GCD may be obtained via the Euclidean algorithm.
The above formula results from the fact that
corresponds to multiset intersection of the two multisets (bags) of prime factors (with multiplicity), while
corresponds to multiset union (which amounts to multiset addition, here performed multiplicatively as
, minus bag intersection, here performed multiplicatively via division by
) of the two bags of prime factors (with multiplicity).
Since (using the inclusion-exclusion principle)
![{\displaystyle m_{1}+m_{2}+m_{3}={\rm {max}}(m_{1},m_{2},m_{3})\,+\,\left\{{\Big [}\min(m_{1},m_{2})+\min(m_{1},m_{3})+\min(m_{2},m_{3}){\Big ]}\,-\,{\rm {min}}(m_{1},m_{2},m_{3})\right\},\quad m_{1}\leq m_{2}\leq m_{3},\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/eb066cc0e19ab747e07569ef1a02bffaef8a0ed7)
we then have
![{\displaystyle |m_{1}m_{2}m_{3}|={\rm {lcm}}(m_{1},m_{2},m_{3})\,\cdot \,\left\{{\frac {\gcd(m_{1},m_{2})~\gcd(m_{1},m_{3})~\gcd(m_{2},m_{3})}{\gcd(m_{1},m_{2},m_{3})}}\right\},\quad m_{1}m_{2}m_{3}\neq 0.\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/c4c51e27837ab53b17d3fc2d36f516a8fa8226c5)
Finally, since (using the inclusion-exclusion principle)
![{\displaystyle \sum _{i=1}^{n}m_{i}={\rm {max}}(m_{1},\ldots ,m_{n})\,+\,\left\{\left[\sum _{i<j}\min(m_{i},m_{j})\right]\,-\,\left[\sum _{i<j<k}\min(m_{i},m_{j},m_{k})\right]\,+\,\cdots \,+\,(-1)^{n}~{\rm {min}}(m_{1},\ldots ,m_{n})\right\},\quad m_{1}\leq \cdots \leq m_{n},\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/cbf881021c8cc75b72816f5d798f16cec2efb6cb)
we then have
![{\displaystyle \left|\prod _{i=1}^{n}m_{i}\right|={\rm {lcm}}(m_{1},\ldots ,m_{n})\,\cdot \,\left\{\left[\prod _{i<j}\gcd(m_{i},m_{j})\right]\,\cdot \,\left[\prod _{i<j<k}\gcd(m_{i},m_{j},m_{k})\right]^{-1}\,\cdot \,\ldots \,\cdot \,[\gcd(m_{1},\cdots ,m_{n})]^{(-1)^{n}}\right\},\quad \prod _{i=1}^{n}m_{i}\neq 0.\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ef02caca80ea0578248002619747f81a25709df5)
Examples
- {{lcm|1}} = 1
- {{lcm|144}} = 144
- {{lcm|1|144}} = 144
- {{lcm|144|2988}} = 11952
- {{lcm|2988|37116}} = 3080628
- {{lcm|25|625}} = 625
- {{lcm|544|119}} = 3808
Sequences
A003418 a(0) = 1; for n ≥ 1, a(n) = least common multiple (or lcm) of {1, 2, ..., n}.
- {1, 1, 2, 6, 12, 60, 60, 420, 840, 2520, 2520, 27720, 27720, 360360, 360360, 360360, 720720, 12252240, 12252240, 232792560, 232792560, 232792560, 232792560, 5354228880, ...}
A014963 Exponential of Mangoldt function M(n): a(n) = 1 unless n is a prime or prime power when a(n) = that prime. (A003418(n) / A003418(n-1), n ≥ 1.)
- {1, 2, 3, 2, 5, 1, 7, 2, 3, 1, 11, 1, 13, 1, 1, 2, 17, 1, 19, 1, 1, 1, 23, 1, 5, 1, 3, 1, 29, 1, 31, 2, 1, 1, 1, 1, 37, 1, 1, 1, 41, 1, 43, 1, 1, 1, 47, 1, 7, 1, 1, 1, 53, 1, ...}
A002944 LCM{1, 2, ..., n} / n, n ≥ 1.
- {1, 1, 2, 3, 12, 10, 60, 105, 280, 252, 2520, 2310, 27720, 25740, 24024, 45045, 720720, 680680, 12252240, 11639628, 11085360, 10581480, 232792560, 223092870, 1070845776, ...}
A099946 LCM{1, 2, ..., n} / (n*(n-1)), n ≥ 2.
- {1, 1, 1, 3, 2, 10, 15, 35, 28, 252, 210, 2310, 1980, 1716, 3003, 45045, 40040, 680680, 612612, 554268, 503880, 10581480, 9699690, 44618574, 41186376, 114406600, ...}
A025527 a(n) = n! / LCM{1,2,...,n} = (n-1)! / LCM{C(n-1,0), C(n-1,1), ..., C(n-1,n-1)}.
- {1, 1, 1, 2, 2, 12, 12, 48, 144, 1440, 1440, 17280, 17280, 241920, 3628800, 29030400, 29030400, 522547200, 522547200, 10450944000, 219469824000, 4828336128000, ...}
See also