Least Common Multiples

Common Multiples

Let $a$ and $b$ be nonzero integers. An integer $m$ is called a common multiple of $a$ and $b$ if

and

For example, the positive multiples of $6$ are

and the positive multiples of $8$ are

Their positive common multiples begin with

The smallest positive common multiple is $24$. Hence

Definition

The least common multiple of two nonzero integers $a$ and $b$ is the smallest positive integer $m$ such that

and

It is denoted by

As with greatest common divisors, signs are ignored:

For example,

The least common multiple is always positive.

Existence

The least common multiple always exists for nonzero integers.

Indeed,

is a positive common multiple of $a$ and $b$, since both $a$ and $b$ divide $ab$. Therefore the set of positive common multiples is nonempty.

By the well-ordering principle, every nonempty subset of $\mathbb{N}$ has a least element. Hence the least common multiple exists.

Basic Examples

If one integer divides the other, the least common multiple is the larger absolute value. For example,

If two integers are coprime, then their least common multiple is their product:

For instance,

Although $9$ is composite, it shares no prime factor with $7$, so the product is already the smallest common multiple.

Prime Factorization View

Prime factorization gives a direct way to compute least common multiples.

Suppose

and

The least common multiple must contain enough prime powers to be divisible by both numbers. Therefore it uses the larger exponent of each prime appearing in either factorization:

In general, the least common multiple contains each prime appearing in either integer, with the larger exponent chosen.

This complements the greatest common divisor, which uses the smaller exponent.

Relation with the Greatest Common Divisor

For nonzero integers $a$ and $b$, the greatest common divisor and least common multiple satisfy

Equivalently,

For example,

Hence

This formula is often the most efficient way to compute an lcm once the gcd is known.

Divisibility Characterization

The least common multiple has a universal divisibility property.

If

then every common multiple of $a$ and $b$ is divisible by $m$.

That is, if

and

then

For example, since

every integer divisible by both $6$ and $8$ is divisible by $24$.

This property explains why the least common multiple is not merely the smallest common multiple. It is the fundamental generator of all common multiples.

LCM of Several Integers

The least common multiple extends naturally to more than two integers.

For nonzero integers

the number

is the smallest positive integer divisible by each $a_i$.

For example,

One may compute it iteratively:

This follows from the divisibility characterization of the least common multiple.

Common Denominators

Least common multiples arise naturally when adding fractions.

To add

one chooses a common denominator divisible by both $6$ and $8$. The least such positive denominator is

Thus

The lcm gives the smallest common denominator and keeps arithmetic as simple as possible.

Role in Number Theory

Least common multiples measure shared periodicity. If one process repeats every $a$ steps and another repeats every $b$ steps, then both repeat together every

steps.

This makes the lcm important in modular arithmetic, congruence systems, cyclic groups, and periodic sequences.

Together, gcd and lcm express two complementary aspects of divisibility. The greatest common divisor measures common factors. The least common multiple measures common multiples. Both are essential tools for organizing the arithmetic structure of the integers.