Least Common Multiple

Introduction

The Least Common Multiple (LCM) is closely related to the GCD and is extremely useful in many mathematical and real-world applications, especially when dealing with fractions, scheduling, and periodic events.

Definition

The least common multiple (LCM) of two positive integers a and b is the smallest positive integer that is divisible by both a and b.

Notation: lcm(a, b) or sometimes [a, b]

Formal Definition: lcm(a, b) is the smallest positive integer m such that:

• a | m (a divides m)
• b | m (b divides m)

Examples

Example 1: lcm(4, 6)

Method 1 - Listing Multiples:

• Multiples of 4: 4, 8, 12, 16, 20, 24, 28, 32, 36…
• Multiples of 6: 6, 12, 18, 24, 30, 36, 42…
• Common multiples: 12, 24, 36, …
• Smallest common multiple: 12

lcm(4, 6) = 12

Example 2: lcm(10, 15)

Listing Multiples:

• Multiples of 10: 10, 20, 30, 40, 50, 60, 70…
• Multiples of 15: 15, 30, 45, 60, 75…
• Smallest common multiple: 30

lcm(10, 15) = 30

Example 3: lcm(7, 13)

• These are both prime and coprime (gcd = 1)
• lcm(7, 13) = 7 × 13 = 91

Note: When gcd(a, b) = 1, then lcm(a, b) = a × b

Example 4: lcm(12, 18)

• Multiples of 12: 12, 24, 36, 48, 60, 72…
• Multiples of 18: 18, 36, 54, 72, 90…
• lcm(12, 18) = 36

Methods for Finding LCM

Method 1: Listing Multiples

List multiples of each number until you find the smallest common one.

Pros: Simple and intuitive Cons: Time-consuming for large numbers

Method 2: Using Prime Factorization

Express both numbers as products of primes, then take the product of all primes with their highest exponents.

Example 1: lcm(60, 84)

Step 1: Prime factorization

• 60 = 2² × 3 × 5
• 84 = 2² × 3 × 7

Step 2: Take each prime with maximum exponent

• 2: max(2, 2) = 2 → 2²
• 3: max(1, 1) = 1 → 3¹
• 5: appears only in 60 → 5¹
• 7: appears only in 84 → 7¹

Step 3: lcm(60, 84) = 2² × 3 × 5 × 7 = 4 × 3 × 5 × 7 = 420

Example 2: lcm(48, 180)

• 48 = 2⁴ × 3
• 180 = 2² × 3² × 5
• lcm = 2⁴ × 3² × 5 = 16 × 9 × 5 = 720

Example 3: lcm(12, 18, 24)

• 12 = 2² × 3
• 18 = 2 × 3²
• 24 = 2³ × 3
• lcm = 2³ × 3² = 8 × 9 = 72

Method 3: Using GCD Formula

Important Formula:

lcm(a, b) = (a × b) / gcd(a, b)

Or equivalently: gcd(a, b) × lcm(a, b) = a × b

Example 1: lcm(12, 18)

Step 1: Find gcd(12, 18)

• Using Euclidean algorithm:
  • gcd(12, 18) = gcd(12, 6) = gcd(6, 0) = 6

Step 2: Use formula

• lcm(12, 18) = (12 × 18) / 6 = 216 / 6 = 36

Example 2: lcm(48, 18)

• gcd(48, 18) = 6
• lcm(48, 18) = (48 × 18) / 6 = 864 / 6 = 144

Example 3: lcm(15, 25)

• gcd(15, 25) = 5
• lcm(15, 25) = (15 × 25) / 5 = 375 / 5 = 75

Why This Formula Works:

If a = gcd(a,b) × m and b = gcd(a,b) × n where gcd(m, n) = 1, then: lcm(a, b) = gcd(a,b) × m × n = (a × b) / gcd(a, b)

Properties of LCM

Property 1: Commutative

lcm(a, b) = lcm(b, a)

Property 2: Relation with GCD

gcd(a, b) × lcm(a, b) = a × b

Property 3: When GCD = 1

If gcd(a, b) = 1 (relatively prime), then lcm(a, b) = a × b

Example: lcm(7, 11) = 7 × 11 = 77

Property 4: Divisibility

If a | b, then lcm(a, b) = b

Example: lcm(6, 18) = 18 (because 6 | 18)

Property 5: LCM with 1

lcm(a, 1) = a for any positive integer a

Property 6: LCM with Itself

lcm(a, a) = a

Property 7: Multiple Property

Both a and b divide lcm(a, b)

Property 8: Minimum Property

If m is any common multiple of a and b, then lcm(a, b) | m

LCM of More Than Two Numbers

Property: lcm(a, b, c) = lcm(lcm(a, b), c)

Example 1: lcm(4, 6, 8)

Step 1: lcm(4, 6)

• 4 = 2²
• 6 = 2 × 3
• lcm(4, 6) = 2² × 3 = 12

Step 2: lcm(12, 8)

• 12 = 2² × 3
• 8 = 2³
• lcm(12, 8) = 2³ × 3 = 24

Example 2: lcm(3, 5, 7)

• All are pairwise coprime
• lcm(3, 5, 7) = 3 × 5 × 7 = 105

Example 3: lcm(12, 15, 20)

• 12 = 2² × 3
• 15 = 3 × 5
• 20 = 2² × 5
• lcm = 2² × 3 × 5 = 4 × 3 × 5 = 60

Applications of LCM

Application 1: Adding/Subtracting Fractions

To add fractions with different denominators, find the LCM of the denominators.

Example: 1/4 + 1/6

• lcm(4, 6) = 12
• 1/4 = 3/12
• 1/6 = 2/12
• 1/4 + 1/6 = 3/12 + 2/12 = 5/12

Application 2: Scheduling Problems

Problem: A bus leaves station A every 15 minutes, and another bus leaves station B every 20 minutes. If both buses leave at 8:00 AM, when do they next leave together?

Solution:

• lcm(15, 20) = 60 minutes = 1 hour
• They next leave together at 9:00 AM

Example 2: Three bells ring at intervals of 6, 8, and 12 minutes. If they ring together at noon, when do they next ring together?

• lcm(6, 8, 12) = 24 minutes
• Next time: 12:24 PM

Application 3: Gear Problems

Problem: Two gears with 12 and 18 teeth are interlocked. How many rotations until they return to the starting position?

Solution:

• lcm(12, 18) = 36 teeth must pass
• First gear: 36/12 = 3 rotations
• Second gear: 36/18 = 2 rotations

Application 4: Pattern Repetition

Problem: Wallpaper pattern A repeats every 8 inches, pattern B every 12 inches. After how many inches do both patterns repeat together?

Solution:

• lcm(8, 12) = 24 inches

Comparing GCD and LCM

Worked Examples

Example 1: Complete Problem

Find gcd and lcm of 36 and 60.

Prime Factorization:

• 36 = 2² × 3²
• 60 = 2² × 3 × 5

GCD (minimum exponents):

• gcd(36, 60) = 2² × 3 = 4 × 3 = 12

LCM (maximum exponents):

• lcm(36, 60) = 2² × 3² × 5 = 4 × 9 × 5 = 180

Verification:

• gcd × lcm = 12 × 180 = 2160
• a × b = 36 × 60 = 2160 ✓

Example 2: Word Problem

Two runners are training on a circular track. One completes a lap in 6 minutes, the other in 8 minutes. If they start together, after how many minutes will they be together at the starting point again?

Solution:

• Need lcm(6, 8)
• 6 = 2 × 3
• 8 = 2³
• lcm(6, 8) = 2³ × 3 = 8 × 3 = 24 minutes

Check:

• First runner: 24/6 = 4 laps
• Second runner: 24/8 = 3 laps
• Both back at start ✓

Example 3: Three Numbers

Find lcm(12, 15, 20)

Prime Factorization:

• 12 = 2² × 3
• 15 = 3 × 5
• 20 = 2² × 5

LCM:

• lcm = 2² × 3 × 5 = 4 × 3 × 5 = 60

Special Cases

Case 1: One Number Divides the Other

If a | b, then lcm(a, b) = b

Example: lcm(5, 25) = 25

Case 2: Relatively Prime Numbers

If gcd(a, b) = 1, then lcm(a, b) = a × b

Example: lcm(9, 16) = 144

Case 3: Consecutive Integers

For consecutive integers a and a+1: lcm(a, a+1) = a(a+1)

Example: lcm(7, 8) = 56

Case 4: Powers of Same Prime

lcm(pᵃ, pᵇ) = p^max(m,n)

Example: lcm(2³, 2⁵) = 2⁵ = 32

Key Points for Exams

1. LCM is the smallest common multiple
2. Use prime factorization with maximum exponents
3. lcm(a,b) = a×b / gcd(a,b) (very useful!)
4. When gcd = 1, lcm = a×b
5. gcd × lcm = a × b (verification formula)
6. lcm ≥ max(a, b) always
7. For more than 2 numbers: compute pairwise
8. Common in word problems - scheduling, patterns
9. Opposite of GCD: GCD uses min, LCM uses max exponents
10. Practice both methods: prime factorization and GCD formula

Practice Problems

1. Find lcm(24, 36) using: a) Listing multiples b) Prime factorization c) GCD formula

2. Find lcm(15, 25, 30)

3. If gcd(a, b) = 6 and lcm(a, b) = 72, find a and b.

4. Three traffic lights change after 48, 72, and 108 seconds. If they change simultaneously at 9:00 AM, when do they next change together?

5. Prove that for any integers a and b: lcm(a, b) × gcd(a, b) = a × b

6. Find the smallest number divisible by 2, 3, 4, 5, and 6.

7. Two cog wheels have 36 and 48 teeth. How many rotations until they return to starting position?

8. If lcm(a, 12) = 36 and gcd(a, 12) = 4, find a.

9. Find lcm(2³ × 3² × 5, 2² × 3³ × 7)

10. Show that lcm(a, b, c) × gcd(a, b, c) ≤ abc