Number Theory • Topic 7

LCM (Least Common Multiple)

The LCM is the smallest common "container" for two numbers.

Definition

Definition (LCM)

The least common multiple of non-zero integers

a

and

b

, denoted

lcm (a, b)

[a, b]

, is the smallest positive integer

m

such that

a ∣ m

and

b ∣ m

Theorem

For any positive integers

a, b

g cd (a, b) \cdot lcm (a, b) = a \cdot b

Proof. Let $a = \prod p_{i}^{α_{i}}$ and $b = \prod p_{i}^{β_{i}}$ .

Since

min (x, y) + max (x, y) = x + y

, the product of exponents sums to

α_{i} + β_{i}

, matching

ab

. ∎

Exercise (Problem 1)

Find the LCM of

12, 18, 30

Exercise (Problem 2)

The product of two numbers is 240 and their GCD is 4. Find the numbers.

Exercise (Problem 3)

Prove that

g cd (a, lcm (b, c)) = lcm (g cd (a, b), g cd (a, c))

. (Distributive law of arithmetic).