Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 86 ยท Number System

HCF and LCM

Learn to find HCF and LCM by factorization, division and the Euclidean method, then solve bells, tiles, rope and remainder problems with a code check.

The HCF (highest common factor, also called GCD or greatest common divisor) of some numbers is the largest number that divides all of them exactly. The LCM (least common multiple) is the smallest number that all of them divide into exactly. Aptitude tests love these two ideas because they hide inside everyday stories: bells that ring together, tiles that must fit a floor without cutting, ropes cut into equal pieces, and numbers that leave the same remainder.

This lesson shows three ways to find them, the important relation between HCF and LCM, and the patterns behind the standard word problems. A script at the end lets you check any answer. You will need the prime factorization from Factors, Multiples and Counting Divisors.

Finding HCF and LCM

Method 1: prime factorization

Write each number as a product of primes. The HCF takes each common prime with its smallest exponent. The LCM takes every prime that appears with its largest exponent.

For 84 = 2ยฒ ร— 3 ร— 7 and 126 = 2 ร— 3ยฒ ร— 7:

  • HCF = 2ยน ร— 3ยน ร— 7ยน = 42
  • LCM = 2ยฒ ร— 3ยฒ ร— 7ยน = 252

This works for any number of numbers. For 12, 18 and 30 (2ยฒ ร— 3, 2 ร— 3ยฒ, 2 ร— 3 ร— 5): HCF = 2 ร— 3 = 6, LCM = 2ยฒ ร— 3ยฒ ร— 5 = 180.

Method 2: common division (for the LCM)

Write the numbers in a row and divide by any prime that divides at least one of them, copying down numbers it does not divide. Stop when only 1s remain. The LCM is the product of all the divisors.

For 12, 18, 30: divide by 2 giving 6, 9, 15; divide by 3 giving 2, 3, 5; divide by 2 giving 1, 3, 5; divide by 3 giving 1, 1, 5; divide by 5 giving 1, 1, 1. The divisors are 2, 3, 2, 3, 5, whose product is 180.

Method 3: the Euclidean algorithm (for the HCF)

For large numbers factorization is slow. The Euclidean method repeatedly replaces the larger number by the remainder of dividing it by the smaller. The last non-zero remainder is the HCF. It works because any number dividing both a and b also divides a โˆ’ k ร— b.

flowchart TB
    A["1071 = 2 x 462 + 147"] --> B["462 = 3 x 147 + 21"]
    B --> C["147 = 7 x 21 + 0"]
    C --> D["HCF = 21"]

Each step divides the previous divisor by the remainder; the last non-zero remainder is the HCF.

For three numbers, find the HCF of the first two, then the HCF of that result with the third.

The HCF-LCM relation

For two numbers a and b:

HCF ร— LCM = a ร— b

Check with 84 and 126: 42 ร— 252 = 10,584 = 84 ร— 126. This relation does not extend to three numbers. It is useful when you know three of the four quantities.

Example: The HCF of two numbers is 12 and their LCM is 336. One number is 48. Find the other. The other number = (12 ร— 336) รท 48 = 84.

Two more consequences:

  • The HCF always divides the LCM.
  • If two numbers are co-prime (HCF = 1), their LCM is simply their product.

Numbers in a given ratio

If two numbers are in the ratio 3 : 4 and their LCM is 240, write them as 3k and 4k, where k is their HCF. Their LCM is 12k, so 12k = 240 and k = 20. The numbers are 60 and 80, and the HCF is 20.

Check your answers with code

The script below uses the Euclidean method for the HCF, derives the LCM from it, and verifies the relation HCF ร— LCM = product for many pairs. Then it checks the examples from this lesson.

JS HCF and LCM checker

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

No output.

The last line prints false, which shows that the HCF ร— LCM relation is only valid for two numbers.

Word problems

Most word problems fall into a handful of types. Recognizing the type tells you whether to use HCF or LCM.

"Together again": LCM

When events repeat at fixed intervals and you want the next time they coincide, use the LCM of the intervals.

Bells: Three bells ring every 20, 30 and 45 seconds. They ring together at 10:00:00. When next? The LCM of 20, 30, 45 is 180 seconds, so at 10:03:00. In 10 minutes, they ring together 1 + โŒŠ600 รท 180โŒ‹ = 1 + 3 = 4 times (counting the start: at 0, 180, 360 and 540 seconds).

Cycles: Two runners take 40 and 56 seconds per lap. They start together; they meet again at the start after LCM(40, 56) = 280 seconds.

"Largest equal piece": HCF

When you must cut or split into equal pieces with nothing left over, and you want the largest piece, use the HCF.

Ropes: Ropes of 24 m, 36 m and 60 m are cut into equal pieces as long as possible. The length is HCF = 12 m, and the number of pieces is 2 + 3 + 5 = 10.

Tiles: A floor 450 cm by 330 cm is covered with square tiles of the largest size, with no cutting. The side is HCF(450, 330) = 30 cm. The number of tiles is (450 รท 30) ร— (330 รท 30) = 15 ร— 11 = 165.

Boxes or groups: 84 apples and 126 oranges are packed into identical boxes with the same mix, using all the fruit. The largest number of boxes is HCF = 42, each with 2 apples and 3 oranges.

"Smallest number that fits": LCM

Least number divisible by several numbers: the LCM. The smallest four-digit number divisible by 12, 15 and 18 uses LCM = 180. Since 1000 รท 180 is a little above 5, the next multiple is 6 ร— 180 = 1,080. The largest four-digit number is 55 ร— 180 = 9,900, since 9,999 รท 180 is a little above 55.

Remainder problems

  1. Same remainder r each time: the number is LCM + r. For the least number leaving remainder 5 when divided by 12, 15 and 20: LCM = 60, so 65.
  2. Different remainders but a constant gap: if divisor โˆ’ remainder is always the same k, the number is LCM โˆ’ k. For divisors 12, 15, 20 with remainders 7, 10, 15 the gap is 5 each time, so the least number is 60 โˆ’ 5 = 55. Check: 55 = 4 ร— 12 + 7 = 3 ร— 15 + 10 = 2 ร— 20 + 15.
  3. Largest divisor leaving the same remainder: take the HCF of the differences. To find the largest number that divides 1,305, 4,665 and 6,905 and leaves the same remainder each time, compute 4,665 โˆ’ 1,305 = 3,360 and 6,905 โˆ’ 4,665 = 2,240. HCF(3,360, 2,240) = 1,120. Indeed each of the three numbers leaves remainder 185.

Why does the difference trick work? If d divides a โˆ’ r and b โˆ’ r, then d divides (b โˆ’ r) โˆ’ (a โˆ’ r) = b โˆ’ a.

HCF and LCM of fractions

For fractions in lowest terms:

HCF = HCF of numerators รท LCM of denominators LCM = LCM of numerators รท HCF of denominators

For 2/3, 8/9, 16/27: HCF = HCF(2, 8, 16) รท LCM(3, 9, 27) = 2/27, and LCM = LCM(2, 8, 16) รท HCF(3, 9, 27) = 16/3.

For decimals, remove the decimal points by multiplying by a power of 10, find the HCF or LCM of the whole numbers, then divide by the same power of 10. For 0.6 and 0.45, write 0.60 and 0.45 and multiply by 100 to get 60 and 45. Their HCF is 15, so the HCF of the decimals is 0.15.

A second check: bells in code

Simulating the bell problem second by second confirms the LCM answer without any formulas.

JS Bells ringing together

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

No output.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the HCF and LCM of 36 and 48?

    36 = 2^2 x 3^2 and 48 = 2^4 x 3. HCF = 2^2 x 3 = 12, LCM = 2^4 x 3^2 = 144. Check: 12 x 144 = 1,728 = 36 x 48.
  2. 2. The HCF of two numbers is 16 and their LCM is 480. If one number is 96, what is the other?

    Other number = (16 x 480) / 96 = 7,680 / 96 = 80.
  3. 3. Three lights flash every 12, 15 and 18 seconds. They flash together now. After how many seconds will they next flash together?

    The LCM of 12, 15 and 18 is 180 seconds (12 = 2^2 x 3, 15 = 3 x 5, 18 = 2 x 3^2, so 2^2 x 3^2 x 5 = 180).
  4. 4. What is the least number that leaves remainder 3 when divided by 8, 12 and 20?

    LCM(8, 12, 20) = 120, so the number is 120 + 3 = 123.
  5. 5. A hall 600 cm by 480 cm is paved with the largest possible square tiles with no cutting. How many tiles are needed?

    HCF(600, 480) = 120 cm. Tiles = (600 / 120) x (480 / 120) = 5 x 4 = 20.

Summary

  • HCF takes common primes with the smallest exponent; LCM takes all primes with the largest exponent.
  • The Euclidean algorithm finds the HCF of large numbers by repeated remainders.
  • For two numbers, HCF ร— LCM = their product. This fails for three or more.
  • "Together again" and "smallest number that fits" problems use LCM; "largest equal piece" problems use HCF.
  • Same remainder r: LCM + r. Constant gap k between divisor and remainder: LCM โˆ’ k. Same remainder with the largest divisor: HCF of the differences.
  • For fractions: HCF = HCF of numerators รท LCM of denominators, and the reverse for the LCM.

Next: Remainders and Cyclicity, where you will find remainders of huge powers and last digits of big numbers.