MathAlgorithmaka least common multiple, lowest common multiple

LCM (Least Common Multiple)

Compute the least common multiple as a / gcd(a, b) * b, dividing before multiplying to avoid overflow.

▶ VisualizePattern: Math & Number TheoryPractice (2)
Progress

Overview

The least common multiple lcm(a, b) is the smallest positive integer divisible by both. It is computed through the gcd: lcm(a, b) = |a · b| / gcd(a, b). For lcm(4, 6): gcd = 2, so lcm = 24 / 2 = 12.

The order of operations matters in fixed-width integers: compute a / gcd(a, b) * b, never a * b / gcd, because a * b can overflow even when the lcm fits. With a = b = 3·10^9 in 64-bit, a * b ≈ 9·10^18 is at the edge of int64 while the lcm is just 3·10^9.

For several numbers fold pairwise: lcm(a, b, c) = lcm(lcm(a, b), c). The lcm of 1..n grows like e^n, so lcm(1..43) already exceeds 2^63 — problems that ask for it use Modular Arithmetic or big integers.

lcmgcdnumber theoryoverflowO(log n)

Intuition

A mental model before the formal terms.

Two gears with 4 and 6 teeth start aligned. After how many teeth do they align again? The 4-gear has period 4, the 6-gear period 6; alignment repeats at the first time both periods divide — 12 teeth. The gcd (2) is the "shared factor" counted twice in 4 · 6, so dividing it out once gives the true period.

How it works

  1. Compute g = gcd(a, b) with Euclid — see GCD (Euclidean Algorithm).
  2. Divide first: a / g is exact because g | a.
  3. Multiply: (a / g) * b. The result is exactly the lcm and is the smallest intermediate possible.
  4. For arrays, fold left with an accumulator starting at 1; check for overflow or reduce modulo m if the problem allows it.

Why it works

Write a = g·a' and b = g·b' with gcd(a', b') = 1. Any common multiple must contain g, all of a' and all of b'; since a' and b' share no factors, the smallest is g·a'·b' = a·b / g.

Equivalently, for each prime p, gcd takes the minimum exponent and lcm the maximum; min + max = sum, so gcd · lcm = a · b.

Recognition

How to tell a problem wants this.

  • "When will both events next coincide", "smallest number divisible by all of", "common period", "align schedules".
  • Problems with fractions that need a common denominator.
  • Counting numbers up to N divisible by a or b: N/a + N/b - N/lcm(a, b) — inclusion-exclusion, see Combinatorics.
“modulo 10^9 + 7” → Math & Number Theory

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related GCD (Euclidean Algorithm) visualization.

abq = a div br = a mod b
252105··
1/8gcd(252, 105): Euclid's insight is gcd(a, b) = gcd(b, a mod b), because any common divisor of a and b also divides a - q·b. We also track coefficients s, t with s·252 + t·105 = current a (extended Euclid).
Current division a = q·b + rValues that become the next (a, b)Finished rowsGCD
PseudocodeLearn GCD (Euclidean Algorithm) →
1(s0, s1), (t0, t1) = (1, 0), (0, 1)   # a = s0·A + t0·B, b = s1·A + t1·B
2while b != 0:
3  q = a div b; r = a mod b
4  a, b = b, r
5  s0, s1 = s1, s0 - q·s1;  t0, t1 = t1, t0 - q·t1
6return a  # gcd; and s0·A + t0·B == gcd
Variables
a252
b105
s1
t0
Complexity
best O(1)
avg O(log min(a, b))
worst O(log min(a, b))
space O(1)
Speed

Pseudocode

1lcm(a, b):
2  if a == 0 or b == 0: return 0
3  return |a| / gcd(a, b) * |b|
4lcm_many(nums):
5  acc = 1
6  for x in nums: acc = lcm(acc, x)
7  return acc

Implementations

1import math
2from functools import reduce
3from typing import List
4 
5 
61 · LCM via GCD, dividing first
7def lcm(a: int, b: int) -> int:
8    """math.lcm (3.9+) does this in C; shown for the algorithm."""
9    if a == 0 or b == 0:
10        return 0  # lcm(0, x) is defined as 0
11    return abs(a // math.gcd(a, b) * b)  # divide first: habit that matters elsewhere
12 
13 
142 · LCM of a list
15def lcm_all(xs: List[int]) -> int:
16    return reduce(lcm, xs, 1)  # lcm is associative; math.lcm(*xs) also works
17 
18 
193 · Demo
20if __name__ == "__main__":
21    assert lcm(4, 6) == 12 == math.lcm(4, 6)
22    assert lcm(21, 6) == 42
23    assert lcm(0, 5) == 0
24    assert lcm(10**18, 2**60) == math.lcm(10**18, 2**60)  # no overflow, ever
25    assert lcm_all([2, 3, 4, 5]) == 60
Walkthrough
  1. a // math.gcd(a, b) * b mirrors the divide-first ordering. In Python it is a micro-optimization (smaller intermediates), not a correctness requirement — ints never overflow.
  2. math.lcm (3.9+) accepts any number of arguments: math.lcm(*xs) replaces the fold.
  3. lcm_all shows the reduce version with identity 1 for pre-3.9 code or custom folds.
  4. The zero guard matches the stdlib convention math.lcm(0, 5) == 0.
Complexity (this implementation)
time O(log min(a, b)) per pair, O(n log M) for a list · space O(1)

Huge results just get slower (O(digits) per op), never wrong.

Language notes
  • math.lcm and math.gcd are C implementations — prefer them over hand-rolled loops.
  • // (floor division) on the positive a // g is exact division here.
  • Because ints are unbounded, folding thousands of coprime values is correct, merely slow.
Common mistakes in this language
  • Using / instead of // and turning the result into a float.
  • Reinventing math.lcm on 3.9+.
  • Porting the overflow paranoia from C++ and complicating code that cannot overflow.
Language differences that matter here
  • Overflow behavior of a * b / g: C++ UB/wraparound, JS/TS silent float rounding above 2^53, Python none. Divide-first (a / g * b) is required in C++ and JS/TS, merely tidy in Python.
  • Stdlib: C++17 std::lcm/std::gcd, Python math.lcm (3.9+, variadic); JS/TS have neither.
  • Failure visibility: C++ overflow is UB, JS/TS return a plausible-looking wrong double (check Number.isSafeInteger), Python cannot fail.
  • Integer division spelling: / on integers (C++), Math.trunc(a / b) or exact float division when g divides a (JS/TS), // (Python), / on bigint (JS/TS) truncates.

Complexity

Best
O(1)
Average
O(log min(a, b))
Worst
O(log min(a, b))
Space
O(1)

Dominated by the gcd. For k numbers, O(k log M) where M bounds the values.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Combining periodic events, finding common denominators, or the smallest step that satisfies several divisibility constraints.
  • Inclusion-exclusion counts of multiples ("numbers ≤ N divisible by a or b").
  • Binary search on the answer for "k-th number divisible by a or b" — the check uses lcm.
Avoid it when
  • When the lcm of many values is needed exactly and grows beyond 64 bits — use a big-integer type or work modulo m if the problem allows.
  • When only the prime-exponent structure matters — take per-prime maxima via Prime Factorization instead of repeated gcd calls.

Alternatives

GCD (Euclidean Algorithm)Prime Factorization

Common mistakes

  • Computing a * b / gcd — the product overflows before the division rescues it.
  • Calling lcm with a zero and dividing by zero in gcd(0, 0); guard zeros explicitly.
  • JavaScript: results above 2^53 silently lose precision; lcmMany of a few large numbers needs BigInt.
  • Using floating-point division (/) in JavaScript when the result should be integral is fine only because g | a; do not use it elsewhere.

Interview patterns

  • Ugly Number III / Nth Magical Number: binary search with n/a + n/b - n/lcm(a, b).
  • Smallest number divisible by 1..n (LCM of a range; needs big ints or a modulus).
  • Gear/light-blink alignment questions reduce to lcm of the periods.

Example problems

Koko Eating BananasmediumCount Primesmedium