Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 39 · Factors, Multiples and Primes

HCF and LCM

Find the highest common factor and lowest common multiple using lists, prime factors and the Euclidean algorithm, and solve real-life HCF and LCM problems.

Two numbers share some factors and some multiples. The highest common factor (HCF) is the biggest number that divides both. The lowest common multiple (LCM) is the smallest number that both divide into. In the US you may see these called the greatest common divisor (GCD) and least common multiple; they are the same thing.

HCF helps you simplify fractions and ratios and cut things into equal pieces. LCM helps you add fractions and find when repeating events line up.

HCF by listing factors

Example 1. Find the HCF of 12 and 18.

  • Factors of 12: 1, 2, 3, 4, 6, 12.
  • Factors of 18: 1, 2, 3, 6, 9, 18.
  • Common factors: 1, 2, 3, 6. The highest is 6.

LCM by listing multiples

Example 2. Find the LCM of 12 and 18.

  • Multiples of 12: 12, 24, 36, 48, ...
  • Multiples of 18: 18, 36, 54, ...
  • The first number in both lists is 36.

Listing works for small numbers. For big ones, use prime factors.

Using prime factors

Write each number in index form (see Prime Factorization).

12 = 2² × 3 and 18 = 2 × 3².

  • HCF takes each prime with the smaller exponent: 2¹ × 3¹ = 6.
  • LCM takes each prime with the larger exponent: 2² × 3² = 36.

Example 3. 120 = 2³ × 3 × 5 and 180 = 2² × 3² × 5.

  • HCF: 2² × 3 × 5 = 60.
  • LCM: 2³ × 3² × 5 = 360.

If a prime appears in only one number, treat its exponent in the other as 0. The HCF then ignores that prime, but the LCM includes it.

A useful relationship

For two numbers a and b:

Text
HCF(a, b) × LCM(a, b) = a × b

Check: 6 × 36 = 216 = 12 × 18. This gives a quick way to find the LCM once you have the HCF: LCM = a × b ÷ HCF. It works for two numbers only, not for three.

The Euclidean algorithm

For large numbers, the Euclidean algorithm finds the HCF without factorizing. Repeat: divide the larger by the smaller and replace the larger with the remainder. When the remainder is 0, the last non-zero number is the HCF.

Example 4. HCF of 252 and 105.

Text
252 = 2 × 105 + 42
105 = 2 × 42  + 21
 42 = 2 × 21  + 0

The last non-zero remainder is 21, so HCF(252, 105) = 21.

Why it works: any number dividing both a and b also divides the remainder a - q·b, so the common divisors of the pair do not change from step to step.

Python HCF by Euclid, LCM from the relationship

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The function prints each division step, so you can follow the algorithm. The last line compares with the standard library.

Word problems

Spot the clue words.

  • HCF appears when you split into equal groups or cut into the largest equal pieces.
  • LCM appears when events repeat and you ask when they next happen together.

Example 5 (HCF). A rope of 84 m and another of 126 m are cut into equal pieces of the greatest possible length, with none left over. The HCF of 84 and 126 is 42, so each piece is 42 m, giving 2 and 3 pieces.

Example 6 (LCM). One bus leaves a station every 12 minutes and another every 18 minutes. They leave together at 8:00. They next leave together after 36 minutes, at 8:36.

Python When do the buses meet again?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Three numbers

For three or more numbers, use prime factors (smallest exponent for HCF, largest for LCM), or apply the two-number method twice: LCM(a, b, c) = LCM(LCM(a, b), c). The product rule does not extend to three numbers.

Co-prime numbers have HCF 1. For them, LCM = a × b. For example LCM(8, 15) = 120.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the HCF of 30 and 45?

    30 = 2 × 3 × 5 and 45 = 3² × 5. The shared part with smallest exponents is 3 × 5 = 15.
  2. 2. What is the LCM of 6 and 8?

    6 = 2 × 3 and 8 = 2³, so the LCM is 2³ × 3 = 24. (The product 48 is not the LCM because 6 and 8 share the factor 2.)
  3. 3. Two numbers have HCF 4 and LCM 60. One number is 12. What is the other?

    HCF × LCM = a × b, so 4 × 60 = 12 × b, and b = 240 ÷ 12 = 20.
  4. 4. Cakes come in boxes of 8 and rolls in packs of 12. What is the smallest number of items you can buy of each so the counts are equal?

    You need a common multiple of 8 and 12; the lowest is 24.

Summary

  • HCF is the largest common factor; LCM is the smallest common multiple.
  • With prime factors, take the smaller exponents for HCF and the larger for LCM.
  • For two numbers, HCF × LCM = a × b.
  • The Euclidean algorithm finds the HCF using repeated division with remainders.
  • HCF suits "split equally" problems; LCM suits "repeat together" problems.

Next: Powers and Index Laws