AFCAT Numerical Ability · LCM and HCF

Greatest and Least Number Problems: Tiles, Bells and Remainders

The greatest number that divides or measures a set of quantities is their HCF; the least number that they all divide, or the time when repeating events coincide, is their LCM; remainders and digit limits shift the answer by a known amount.

All LCM and HCF notes

Why this matters

This is the largest page of the chapter and holds both of its HARD questions, plus an AFCAT question from 2016. The first decision is HCF or LCM: greatest that divides points to the HCF, least that is divisible or the next time together points to the LCM. Most marks are lost after that, by forgetting to take off or add back a remainder, or by missing the digit limit.

Concept 1 of 4: The greatest number that divides or measures: tiles, containers and remainders

A measure that fits each quantity exactly is a common factor of them all, and the biggest such measure is their HCF. If each division is to leave something over, remove what is left over first, and the rest must divide exactly.

Definition

The largest container, rope length or weight that measures several amounts exactly: the HCF of the amounts.
The largest square tile for an $l \times b$ floor: side $s = \text{HCF}(l, b)$ in one unit; the number of tiles is $\dfrac ls \times \dfrac bs$ .
The largest number dividing $a, b, c$ and leaving remainder $r$ in each: $\text{HCF}(a - r, b - r, c - r)$ .
Leaving remainders $r_1, r_2, r_3$ : $\text{HCF}(a - r_1, b - r_2, c - r_3)$ .
Leaving the same remainder, not stated: the HCF of the differences $b - a$ , $c - b$ , $c - a$ .

Greatest divisor leaving remainders

\text{HCF}(a - r_1,\; b - r_2,\; c - r_3)

Worked example

Find the largest number that divides 398, 436 and 542, leaving remainders 7, 11 and 15.

Practice this conceptself-check · 4 quick reps

The same idea in a practice question:

Practice questionModerate

Example 1 · LCM and HCF · Greatest and Least Number Problems

What is the largest number which can divide 1356, 1868 and 2764 leaving 12 as remainder in each case?

Take the remainder off first

The HCF of the original numbers answers a different question. If each division must leave 7, the divisor goes exactly into each number minus 7.

One unit before the HCF

A floor 3 m 60 cm by 2 m 40 cm is 360 cm by 240 cm, so the largest tile is 120 cm. Mixing metres and centimetres gives a meaningless HCF.

Drill 4 more on the greatest number that divides or measures: tiles, containers and remainders

Concept 2 of 4: Bells, lights and laps: when events coincide again

A bell that tolls every 6 seconds tolls at every multiple of 6. Several bells toll together at the common multiples of their intervals, so the first time after the start is the LCM.

Definition

Events repeating every $a, b, c$ units coincide every $\text{LCM}(a, b, c)$ units.
Runners who start together are back at the start together after the LCM of their lap times.
In a span of time $T$ , they coincide $\left\lfloor \dfrac TL \right\rfloor$ times after the start, and one more time if the start is counted.
Work in one unit (seconds or minutes), then turn the LCM into a clock time at the end.

Next time together

\text{next meeting} = \text{start} + \text{LCM}(a, b, c)

Worked example

Three bells toll every 6, 8 and 12 seconds and toll together at the start. How many times do they toll together in the next 30 minutes?

Practice this conceptself-check · 4 quick reps

The same idea in a practice question:

Practice questionEasy

Example 2 · LCM and HCF · Greatest and Least Number Problems

Three electronic devices make a beep after every 48 s, 72 s and 108 s, respectively. They beeped together at 10 am. The time when they will next make a beep together at the earliest is

Counting the start

If bells coincide every 15 minutes, in 2 hours they coincide 8 times after the start, and 9 times if the start counts. Read which one the question asks.

Together again is an LCM

The next time together is the smallest common multiple of the intervals. Adding the intervals, or taking their HCF, gives a time when they are not all ringing.

Drill 3 more on bells, lights and laps: when events coincide again

Concept 3 of 4: The least number leaving given remainders

A number that leaves remainder 4 when divided by several numbers is 4 more than a common multiple of them. The least such number is the LCM plus 4. When each remainder falls short of its divisor by the same amount, the number is that amount less than a multiple of the LCM.

Definition

Least number leaving remainder $r$ with each of $a, b, c$ : $\text{LCM}(a, b, c) + r$ .
Remainders each $k$ less than the divisors: $\text{LCM} - k$ .
Greatest $n$ -digit number leaving remainder $r$ : the largest $n$ -digit multiple of the LCM, plus $r$ . Check it still has $n$ digits.
With one more condition, such as divisible by 7: try $L \times 1 + r$ , $L \times 2 + r$ , and so on until it holds.

Least number with a remainder

N = \text{LCM}(a, b, c) \times m + r, \quad m = 1, 2, 3, \ldots

Worked example

Find the least number which leaves remainder 4 when divided by 8, 9 and 15.

Practice this conceptself-check · 4 quick reps

The same idea in a practice question:

Practice questionModerate

Example 3 · LCM and HCF · Greatest and Least Number Problems

The least number which when divided by 20, 25, 35 and 40 leaves the remainders 14, 19, 29 and 34, respectively is

Different remainders, same gap

When the remainders differ, compare each with its divisor. Remainders 3, 8 and 13 on 7, 12 and 17 are each 4 short, so subtract 4 from the LCM; adding any of the remainders is wrong.

Adding the remainder can add a digit

For the greatest 3-digit number leaving remainder 7 on division by 333, 999 plus 7 has four digits. Step back one multiple:

666 + 7 = 673

Drill 3 more on the least number leaving given remainders

Concept 4 of 4: Multiples of the LCM in a range or with a condition

Divisible by each of several numbers means divisible by their LCM. Every question here then asks for one particular multiple of the LCM: the first with four digits, the last below a bound, the one nearest a given number, or the smallest that is a perfect square.

Definition

Divisible by all of $a, b, c$ means a multiple of $L = \text{LCM}(a, b, c)$ , not of their product.
Least $n$ -digit multiple: divide the smallest $n$ -digit number by $L$ , round up, multiply back. Greatest: divide the largest, round down.
Least number to add to $N$ : the next multiple of $L$ minus $N$ . Least number to subtract: the remainder of $N \div L$ .
Largest number to subtract so that a positive multiple of $L$ is left: $N - L$ .
Multiples of $L$ below $N$ : $\left\lfloor \dfrac{N - 1}{L} \right\rfloor$ .
Smallest multiple of $L$ that is a perfect square: multiply in whatever primes make every power even.

Multiples of the LCM

\text{multiple} = L \times m, \quad L = \text{LCM}(a, b, c)

Worked example

Find the least and the greatest 4-digit numbers divisible by 12, 15, 20 and 27.

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

AFCAT · 2016 · AFCAT (I) 2016 — Numerical Ability · 01-403Moderate

Example 4 · LCM and HCF · Greatest and Least Number Problems

Find the largest number which when subtracted from 10000, the remainder is divisible by 32, 36, 48 and 54.

Divisible by all is the LCM, not the product

A number divisible by 6 and 10 is a multiple of 30. Using the product, 60, misses 30 and 90.

Largest to subtract leaves one copy, not zero

Subtracting the whole number leaves 0, which every number divides, but the question means a positive result. Leave the smallest positive multiple, the LCM itself.

Read which number is bounded

'The greatest 5-digit number to be added' bounds the number added, not the sum. The sum can be as large as the given number plus 99,999.

Drill 5 more on multiples of the lcm in a range or with a condition

Summary — formulas & gotchas at a glance

A revision cheat-sheet for the formulas and gotchas above. Click any concept name to jump back to its full explanation.

Formulas (4)

The greatest number that divides or measures: tiles, containers and remainders
Greatest divisor leaving remainders
$\text{HCF}(a - r_1,\; b - r_2,\; c - r_3)$
Bells, lights and laps: when events coincide again
Next time together
$\text{next meeting} = \text{start} + \text{LCM}(a, b, c)$
The least number leaving given remainders
Least number with a remainder
$N = \text{LCM}(a, b, c) \times m + r, \quad m = 1, 2, 3, \ldots$
Multiples of the LCM in a range or with a condition
Multiples of the LCM
$\text{multiple} = L \times m, \quad L = \text{LCM}(a, b, c)$

Watch out for (9)

Take the remainder off first
→ The greatest number that divides or measures: tiles, containers and remainders
One unit before the HCF
→ The greatest number that divides or measures: tiles, containers and remainders
Counting the start
→ Bells, lights and laps: when events coincide again
Together again is an LCM
→ Bells, lights and laps: when events coincide again
Different remainders, same gap
→ The least number leaving given remainders
Adding the remainder can add a digit
→ The least number leaving given remainders
Divisible by all is the LCM, not the product
→ Multiples of the LCM in a range or with a condition
Largest to subtract leaves one copy, not zero
→ Multiples of the LCM in a range or with a condition
Read which number is bounded
→ Multiples of the LCM in a range or with a condition

Drill the questions on this topic

19 questions from the bank, with cart and Word export.

Drill all 19 questions