The least common multiple of two or more positive integers is the smallest positive integer that is a multiple of every one of them. It is usually written , or for several inputs. For example, : both 12 and 18 divide 36, and no smaller positive integer has this property. A basic concept in arithmetic and number theory, the least common multiple is used to find common denominators, describe repeating cycles, and solve divisibility problems.
Definition and conventions
For positive integers , an integer is a common multiple if each divides . The notation means that for some integer .
Their least common multiple is therefore
A positive common multiple always exists because the product is one. The least common multiple has the stronger property that it divides every common multiple. Consequently, if , the common multiples are exactly
For negative inputs, signs are ignored:
Here denotes absolute value. A standard extension to zero is
including . This is a convention extending the positive-input definition: there is no positive multiple of zero. It preserves the statement that an LCM is a common multiple dividing every common multiple.
Prime factorization
The fundamental theorem of arithmetic gives a direct way to construct an LCM. Write each positive input as a product of powers of prime numbers. For every prime appearing in any input, take the largest exponent with which it occurs.
If
where all but finitely many exponents are zero, then
For example,
so
This also explains why the result divides every common multiple. Any common multiple must contain at least the prime-power factors required by every input, and hence must contain their maximum exponents.
For several positive integers, the same rule gives
where is the exponent of in the prime factorization of .
Relationship with the greatest common divisor
The LCM is closely related to the greatest common divisor (GCD). For positive integers,
The GCD takes the minimum exponent of each prime, while the LCM takes the maximum. Since
their product contains exactly the prime factors of .
For nonzero integers, this yields
Important special cases include:
If and both are positive, then .
If , then .
For positive ,
Integers with GCD 1 are called coprime. For several pairwise coprime positive integers, the LCM is their product. Merely having an overall GCD of 1 is not sufficient: 6, 10, and 15 have overall GCD 1, but their LCM is 30 rather than 900.
Computation
Listing multiples
For small numbers, the LCM can be found by listing successive positive multiples. For example:
- Multiples of 6:
- Multiples of 8:
The first shared value is 24. This method illustrates the definition but becomes inefficient when the first common multiple is large.
Using the Euclidean algorithm
For larger integers, an efficient algorithm first computes the GCD with the Euclidean algorithm, then uses
The division is exact. Dividing before multiplying reduces the size of the intermediate result and can avoid overflow when the final answer fits within the available integer range, although the LCM itself may still exceed that range. Zero inputs must be handled separately to avoid division by zero when both inputs are zero.
For example, , so
This method does not require prime factorization.
Several inputs
The LCM is associative:
It can therefore be computed successively:
For instance,
The two-input product formula does not extend simply by dividing the product of all inputs by their overall GCD.
Algebraic and order properties
For nonnegative integers, the LCM operation is commutative, associative, and idempotent:
It also satisfies
and, for any integer ,
Divisibility defines a partial order on the positive integers: precedes when . In this order, the LCM is the least upper bound, also called the join, while the GCD is the greatest lower bound, or meet. This order-theoretic description captures more than numerical minimality: every common multiple is divisible by the LCM.
Applications
Common denominators
For fractions with positive integer denominators, the LCM of the denominators is their least common denominator. For example,
The product of the denominators is also a common denominator, but it may be unnecessarily large. Using the LCM keeps intermediate expressions smaller. It does not guarantee that the resulting fraction is already reduced.
Repeating events
If two events occur together initially and then repeat at intervals of and units, with positive integer , their next simultaneous occurrence is after
units. Thus, events repeating every 12 and 18 minutes coincide again after 36 minutes.
The shared starting point matters. If the events begin at different times, their coincidence is instead a problem about congruences in modular arithmetic. For two integer periods, compatible starting offsets must differ by a multiple of the GCD of the periods. When a coincidence exists, all coincidence times form one congruence class modulo their LCM, as described by the generalized Chinese remainder theorem.
Permutations
In group theory, a permutation decomposes into disjoint cycles. Its order—the smallest positive number of repetitions that returns every element to its original position—is the LCM of its cycle lengths. Disjoint cycles of lengths 4 and 6 therefore give a permutation of order 12.
Generalizations
For nonzero polynomials over a field, a least common multiple is defined by divisibility: it is divisible by every input and divides every common multiple. It is unique only up to multiplication by a nonzero constant; requiring it to be monic, with leading coefficient 1, makes it unique.
The integer construction also has an interpretation using ideals. If denotes the set of all integer multiples of , then
Thus, intersecting the sets of multiples corresponds exactly to taking an LCM. In more general rings, such an intersection need not be generated by a single element, so least common multiples do not exist for every pair of elements.