This site is supported by donations to The OEIS Foundation.

# LCM

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 \scriptstyle m_{i},\,1\,\leq \,i\,\leq \,n,\,}$

${\displaystyle m_{i}=\prod _{j=1}^{\pi (\max(m_{1},\ldots ,m_{n}))}{p_{j}}^{\alpha _{j}(i)},\quad 1\,\leq \,i\,\leq \,n,\,}$

where ${\displaystyle \scriptstyle \pi (m)\,}$ is the number of primes up to ${\displaystyle \scriptstyle m\,}$, and ${\displaystyle \scriptstyle p_{j}\,}$ is the ${\displaystyle \scriptstyle j\,}$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))}\,}$

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))}\,}$

## Formulae

### Formulae relating LCM to GCD

Since

${\displaystyle m+n={\rm {max}}(m,n)\,+\,{\rm {min}}(m,n),\quad m\leq n,\,}$

then the least common multiple (LCM) of two nonzero integers ${\displaystyle \scriptstyle m\,}$ and ${\displaystyle \scriptstyle n\,}$ is related to their greatest common divisor (GCD) by

${\displaystyle |mn|={\rm {lcm}}(m,n)\cdot \gcd(m,n),\quad mn\neq 0,\,}$

where the GCD may be obtained via the Euclidean algorithm.

The above formula results from the fact that ${\displaystyle \scriptstyle \gcd(m,\,n)\,}$ corresponds to multiset intersection of the two multisets (bags) of prime factors (with multiplicity), while ${\displaystyle \scriptstyle {\rm {lcm}}(m,\,n)\,}$ corresponds to multiset union (which amounts to multiset addition, here performed multiplicatively as ${\displaystyle \scriptstyle mn\,}$, minus bag intersection, here performed multiplicatively via division by ${\displaystyle \scriptstyle \gcd(m,\,n)\,}$) 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},\,}$

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.\,}$

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

we then have

${\displaystyle \left|\prod _{i=1}^{n}m_{i}\right|={\rm {lcm}}(m_{1},\ldots ,m_{n})\,\cdot \,\left\{\left[\prod _{i

## 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, ...}