This site is supported by donations to The OEIS Foundation.

# LCM

(Redirected from Least common multiple)

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 $\scriptstyle m_i,\, 1 \,\le\, i \,\le\, n, \,$

$m_i = \prod_{j=1}^{\pi(\max(m_1, \ldots, m_n))} {p_j}^{\alpha_{j}(i)},\quad 1 \,\le\, i \,\le\, n, \,$

where $\scriptstyle \pi(m) \,$ is the number of primes up to $\scriptstyle m \,$, and $\scriptstyle p_j \,$ is the $\scriptstyle j \,$th prime number, we have

$\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

${\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

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

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

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

where the GCD may be obtained via the Euclidean algorithm.

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

Since (using the inclusion-exclusion principle)

$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 \le m_2 \le m_3, \,$

we then have

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

Finally, since (using the inclusion-exclusion principle)

$\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 \le \cdots \le m_n, \,$

we then have

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

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

A002944 LCM{1, 2, ..., n} / n.

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

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