LCM

From OeisWiki

Current revision (unreviewed)

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

LCM

From OeisWiki

Contents

GCD and LCM in terms of the prime factorization

Formulae

Formulae relating LCM to GCD

Examples

Sequences

See also

Views

Personal tools

Navigation

Search

Toolbox