LCM and HCF

There are three methods, and a good student picks the one that suits the numbers.

1. Prime factorisation method. Break every number into primes and write them in power form.

• HCF = product of the common primes, each taken with its lowest power.
• LCM = product of all the primes that appear, each taken with its highest power.

For example, 72 = 2³ × 3², 120 = 2³ × 3 × 5, 180 = 2² × 3² × 5.
HCF: common primes are 2 and 3; lowest powers 2² and 3¹ ⇒ HCF = 4 × 3 = 12.
LCM: primes 2, 3, 5; highest powers 2³, 3², 5¹ ⇒ LCM = 8 × 9 × 5 = 360.

[[fig:0]]

Why the lowest power for HCF? The HCF has to sit inside every number, so it cannot take more 2's than the number with the fewest 2's. Why the highest for LCM? Every number has to sit inside the LCM, so it needs as many 2's as the number with the most 2's.

2. Common division (ladder) method for LCM. Write the numbers in a row and keep dividing by a prime that divides at least two of them; a number that is not divisible comes down as it is. Stop when no two numbers have a common factor. LCM = all divisors on the left × all numbers left at the bottom.

LCM = 2 × 2 × 3 × 2 × 5 × 9 = 1080.

[[fig:1]]

3. Long division (Euclid's) method for HCF. For big numbers whose factors are not obvious, divide the bigger by the smaller, then divide the previous divisor by the remainder, and keep going. When the remainder becomes 0, the last divisor is the HCF.
HCF(391, 667):
667 = 1 × 391 + 276
391 = 1 × 276 + 115
276 = 2 × 115 + 46
115 = 2 × 46 + 23
46 = 2 × 23 + 0 ⇒ HCF = 23
This works because any number that divides two numbers also divides their difference and their remainders. Sometimes the question gives the quotients of this process and asks you to rebuild the numbers. Run the steps backwards, starting from the last divisor.

[[fig:2]]

HCF in the form ax + by. The HCF of two numbers can always be written as (first number) × (some integer) + (second number) × (some integer). If the question fixes one multiplier, find the HCF first and then solve the simple equation for the other. The answer may come out negative, so don't be surprised by a minus sign.

Differences and the HCF. The HCF of some numbers also divides every difference between them. HCF(391, 667) must divide 667 − 391 = 276 = 2² × 3 × 23, and it does: 23. So the HCF can never be bigger than the smallest difference. With three big numbers this saves a lot of work.

Sometimes the question does not give you plain numbers. It gives numbers already broken into prime powers, like 2³ × 3² × 5, or letters like a²b³, or algebraic expressions like x² − 9. The rule stays exactly the same as the factorisation method of Type 1.

Prime-power form. HCF = common bases with the lowest powers; LCM = all bases with the highest powers.
If p = 2³ × 3⁴ × 7 and q = 2⁵ × 3 × 11, then
HCF = 2³ × 3 (7 and 11 are not common, so they are left out)
LCM = 2⁵ × 3⁴ × 7 × 11

[[fig:0]]

The same works with letters when the letters stand for primes. For x = m⁴n and y = m²n³: HCF = m²n, LCM = m⁴n³. Look at the product too: HCF × LCM = m⁶n⁴ = x × y. This is no coincidence, and the next type explains why.

Algebraic expressions. First factorise each expression completely; each factor now plays the role of a prime.

• HCF = product of the common factors with the lowest powers.
• LCM = product of all the factors with the highest powers.

Take x² − 9 = (x − 3)(x + 3) and x² + x − 12 = (x + 4)(x − 3).
HCF = (x − 3), LCM = (x − 3)(x + 3)(x + 4).

[[fig:1]]

Keep these factorisations ready, because these questions are built on them:

• a² − b² = (a − b)(a + b)
• a³ − b³ = (a − b)(a² + ab + b²)
• a³ + b³ = (a + b)(a² − ab + b²)
• (a − b)³ = a³ − 3a²b + 3ab² − b³
• x² + (p + q)x + pq = (x + p)(x + q)

Radhika is asked for the LCM of 2a²b and 6ab³. For the numbers, LCM(2, 6) = 6. For the letters, the highest powers are a² and b³. So the LCM is 6a²b³, and the HCF is 2ab.

You will use this result more than any other in the chapter, so first see why it is true instead of just memorising it.

Take any two numbers and let their HCF be H. Since H divides both, we can write the numbers as
first = H × x, second = H × y,
where x and y have no common factor left, that is, they are co-prime. If they still had one, the HCF would have been bigger than H.

Now the LCM must contain H once, and then x and y, which share nothing. So LCM = H × x × y.

[[fig:0]]

Multiply HCF and LCM: H × (Hxy) = (Hx) × (Hy) = first × second.

HCF × LCM = First number × Second number

Radhika takes 18 and 30. HCF = 6 and LCM = 90. Check: 6 × 90 = 540 and 18 × 30 = 540. Here H = 6, x = 3, y = 5.

[[fig:1]]

Questions use it in three ways:

• Find the other number: other number = HCF × LCMgiven number.
• Find the product: product = HCF × LCM.
• Co-prime numbers: HCF = 1, so LCM = product.

Now an important warning: this rule is for two numbers only. For three numbers, HCF × LCM is generally not the product. Take 2, 4, 8: HCF = 2, LCM = 8, HCF × LCM = 16, but the product is 64.

When the question says "the LCM is k times the HCF", go back to the H, x, y picture: LCM = Hxy, so xy = k. Put this together with the product and the question opens up.

Many short questions test understanding, not calculation. Every one of them comes from the meaning of HCF and LCM that we saw in the foundation.

1. HCF always divides LCM. If HCF = 15, the LCM can be 45, 90, 150 … but never 100 or 160. Turn it around: if LCM = 84, the HCF must be a factor of 84.

[[fig:0]]

2. Combining step by step. HCF(A, B, C) = HCF(HCF(A, B), C) and LCM(A, B, C) = LCM(LCM(A, B), C). So if the question gives only "HCF of A and B is 40 and C = 16", you don't need A and B at all: HCF(A, B, C) = HCF(40, 16) = 8. In the same way, if LCM(A, B) = 14 and LCM(C, D) = 35, then LCM(A, B, C, D) = LCM(14, 35) = 70.

[[fig:1]]

3. When one number divides another. If a divides b, then HCF(a, b) = a and LCM(a, b) = b. So "the LCM of A and B is B" just means that A divides B.

4. Primes and co-primes. For two different primes p and q, HCF = 1 and LCM = pq. So if the LCM of two primes is given, factorise it: LCM = 77 means the primes are 7 and 11. For any two co-prime numbers, HCF = 1 and LCM = product.

5. Multiplying the numbers. If every number is multiplied by k, the HCF and LCM are also multiplied by k: HCF(6a, 6b) = 6 × HCF(a, b). If the numbers pick up new, different primes that they did not have before, those primes join the LCM: if LCM(a, b) = 10 and neither a nor b has the factor 3 or 7, then LCM(3a, 7b) = 3 × 7 × 10 = 210.

6. Using the HCF to get the LCM. For two numbers m and n, LCM = m × nHCF. If HCF = h and n = h × t, then LCM = m × h th = m × t.

Radhika knows that HCF(P, Q) = 45 and R = 30. Without knowing P and Q, she writes HCF(P, Q, R) = HCF(45, 30) = 15.

When the ratio of the numbers is given, write them as multiples of one unknown. If the ratio a : b is in its lowest terms (a and b co-prime), the numbers are ak and bk.

Now see what follows:

• HCF(ak, bk) = k, because a and b share nothing more.
• LCM(ak, bk) = a × b × k, because a and b are co-prime.
• Sum = (a + b)k, difference = (a − b)k, product = abk².

So in a ratio question, k itself is the HCF, and the LCM is k times the product of the ratio terms. Whatever the question gives you (HCF, LCM, sum or HCF × LCM), one equation gives k, and everything else follows.

Radhika's two numbers are in the ratio 2 : 5 and their LCM is 150. Numbers = 2k, 5k; LCM = 2 × 5 × k = 10k = 150 ⇒ k = 15. The numbers are 30 and 75, and their HCF is 15.

[[fig:0]]

Three numbers. For a ratio a : b : c with HCF(a, b, c) = 1, the numbers are ak, bk, ck and their HCF is k. The LCM is k × LCM(a, b, c). It equals k × abc only when a, b, c are pairwise co-prime. For 2 : 3 : 4 the LCM is 12k, not 24k.

[[fig:1]]

One more check: if the ratio is not in lowest terms, reduce it first. A ratio of 6 : 8 is really 3 : 4.

Here the ratio is not given. Instead the question gives the HCF together with the LCM, the sum, the difference or the product. We use the same picture as in Type 3:

Numbers = Hx and Hy, where x and y are co-prime.

Now turn every piece of information into x and y:

• LCM = Hxy ⇒ xy = LCMHCF
• Sum = H(x + y) ⇒ x + y = SumHCF
• Difference = H(x − y) ⇒ x − y = DifferenceHCF
• Product = H²xy ⇒ xy = ProductHCF²

The whole question shrinks to small numbers. "Find two co-prime numbers whose product is 20 and sum is 9" gives 4 and 5, and then you multiply back by H.

Radhika's numbers have HCF 7, LCM 210 and sum 77. xy = 2107 = 30 and x + y = 777 = 11. The co-prime pair with product 30 and sum 11 is 5 and 6, so the numbers are 35 and 42.

[[fig:0]]

Counting pairs. Some questions ask "how many such pairs are possible?". Reduce to x and y in the same way and then count the co-prime pairs.

• If the sum and HCF are given: x + y = SumHCF. List every split of this number and keep only those where x and y are co-prime. For x + y = 10, (1, 9) and (3, 7) work; (2, 8), (4, 6) and (5, 5) do not. So 2 pairs.
• If the product and HCF are given: xy = ProductHCF². List all factor pairs and keep the co-prime ones. For xy = 36, (1, 36) and (4, 9) work; (2, 18), (3, 12) and (6, 6) do not. So 2 pairs.

[[fig:1]]

A useful fact for the product case: the number of co-prime pairs (x, y) with product N is 2^{n − 1}, where n is the number of different primes in N (N > 1, and (x, y) and (y, x) are counted once). For 36 = 2² × 3², n = 2, so there are 2¹ = 2 pairs.

With fractions, first understand what the answer means. The HCF of fractions is the biggest fraction that goes into each given fraction a whole number of times. The LCM of fractions is the smallest fraction that each given fraction goes into a whole number of times.

To go into every fraction exactly, the HCF needs a numerator that divides all the numerators (so take their HCF) and a denominator that all the denominators divide (so take their LCM). The LCM works the other way round:

HCF of fractions = HCF of numeratorsLCM of denominators
LCM of fractions = LCM of numeratorsHCF of denominators

Take 23 and 49.
HCF = HCF(2, 4)LCM(3, 9) = 29. Check: 23 ÷ 29 = 3 and 49 ÷ 29 = 2, both whole numbers.
LCM = LCM(2, 4)HCF(3, 9) = 43. Check: 43 ÷ 23 = 2 and 43 ÷ 49 = 3, again whole numbers.

[[fig:0]]

Reduce every fraction to its lowest terms first. Students forget this more than anything else in this type. 69 and 23 are the same number, so they must give the same answer. The formulas work correctly only when each fraction is in lowest terms; otherwise the LCM formula in particular gives a wrong, bigger answer.

Decimals. Give all the decimals the same number of decimal places, remove the decimal point, find the HCF or LCM of the whole numbers, and put the same number of decimal places back.
HCF and LCM of 0.6, 0.9 and 1.2: these are 6, 9 and 12 tenths. HCF(6, 9, 12) = 3 and LCM = 36. So HCF = 0.3 and LCM = 3.6.
This is the same as writing them as fractions over 10 (or 100) and using the fraction rule.

[[fig:1]]

This whole type rests on one sentence: a number is divisible by each of a, b, c exactly when it is divisible by their LCM. So every question here first becomes "divisible by L", where L is the LCM of the given numbers. After that it is plain division.

Divisible by both 6 and 8? The test number is not 48, because the LCM is 24. A number divisible by 6 and 8 is a multiple of 24. With co-prime pieces you can test separately: divisible by 5 and 9 means divisible by 45, because 5 and 9 are co-prime.

[[fig:0]]

Greatest n-digit number divisible by L. Take the greatest n-digit number, divide by L, and subtract the remainder.
Smallest n-digit number divisible by L. Take the smallest n-digit number, divide by L, and add (L − remainder). If the remainder is 0, the number itself is the answer.

Say Radhika wants numbers divisible by 15, 25 and 40. L = LCM = 600.

• Greatest 4-digit: 9999 = 16 × 600 + 399 ⇒ 9999 − 399 = 9600.
• Smallest 4-digit: 1000 = 1 × 600 + 400 ⇒ 1000 + (600 − 400) = 1200.

[[fig:1]]

Least number to be added to N. Divide N by L. If the remainder is r, add (L − r). If r = 0, the number is already divisible and the least non-negative addition is 0 (it is L only if the question asks for a positive number).
Least number to be subtracted from N. Subtract the remainder r itself.
For N = 2000 and L = 600: 2000 = 3 × 600 + 200. Add 400 (to reach 2400) or subtract 200 (to reach 1800).

[[fig:2]]

The same idea in other words.

• Least number which when increased by 3 is divisible by … ⇒ number + 3 = L ⇒ number = L − 3.
• Least number which when decreased by 3 is divisible by … ⇒ number − 3 = L ⇒ number = L + 3.
• Least number which when doubled is divisible by … ⇒ 2 × number is a multiple of L ⇒ if L is even, the number is L2.
• Sum of all two-digit numbers divisible by a and b ⇒ list the two-digit multiples of L and add them.

A perfect square has every prime in its factorisation with an even power: 144 = 2⁴ × 3², 900 = 2² × 3² × 5².

So to find the least perfect square divisible by some numbers:
1. Find their LCM. The square has to be a multiple of it.
2. Write the LCM in prime-power form.
3. Multiply by the smallest primes needed to make every power even.

Radhika wants the least perfect square divisible by 8 and 27.
LCM(8, 27) = 216 = 2³ × 3³. Both powers are odd, so multiply by 2 × 3 = 6.
Least square = 216 × 6 = 1296 = 2⁴ × 3⁴ = 36².

[[fig:0]]

Why is this the least one? Any square divisible by these numbers is divisible by the LCM, so it contains 2³ and 3³. Being a square, it must then contain at least 2⁴ and 3⁴. So nothing smaller than 1296 is possible.

Least perfect square = LCM × the primes that have odd powers in the LCM. The same idea works for a perfect cube; there you make every power a multiple of 3.

This type also comes as a story: "students can stand in rows of 6, 8 or 9, and their total is a perfect square". The total must be divisible by 6, 8 and 9, so it is exactly this type.

Here the unknown number is the divisor, and it has to be the greatest, so this is HCF territory. Remove the remainders first, so that the divisor divides everything exactly.

Case 1: remainders given (same or different). If d divides a, b, c leaving remainders r₁, r₂, r₃, then d divides (a − r₁), (b − r₂) and (c − r₃) exactly.
Greatest such d = HCF(a − r₁, b − r₂, c − r₃)
For example, the greatest number that divides 62 and 98 leaving remainder 2 in each case is HCF(60, 96) = 12. The greatest number that divides 47 and 83 leaving remainders 2 and 3 is HCF(45, 80) = 5.

[[fig:0]]

One check: the divisor must be bigger than every remainder. A remainder can never be equal to or bigger than the divisor.

Case 2: same remainder, but the remainder is not told. Then use differences. If a = dq₁ + r and b = dq₂ + r, subtracting gives b − a = d(q₂ − q₁). The unknown r cancels out, and d divides the difference.
Greatest d = HCF(b − a, c − b, c − a)
Take 89, 125 and 161. The differences are 36, 36 and 72, so HCF = 36. Check: 89 = 2 × 36 + 17, 125 = 3 × 36 + 17, 161 = 4 × 36 + 17. The same remainder, 17, every time.

[[fig:1]]

You don't need all three differences. Any two of them (say b − a and c − b) are enough, because the third is their sum.

Once d is known, the remainder r is just the remainder of a ÷ d. Some questions then ask for d − r, d + r or the sum of the digits of d.

Now the divisors are given, and the unknown is the number being divided. It is "almost" divisible by all the divisors: it is always r more than a common multiple. So this is LCM territory.

If a number leaves remainder r when divided by a, b and c, then (number − r) is divisible by all of them, so (number − r) is a multiple of L = LCM(a, b, c).

Number = L × k + r (k = 1, 2, 3, …)

[[fig:0]]

• Least such number: choose k from the size the question states, with 0 ≤ r < every divisor. The least non-negative number is r itself (k = 0). When the question means a number bigger than the divisors (the usual "least number" wording), take k = 1: L + r. For divisors 6, 8, 12 and remainder 5: L = 24, so the least non-negative number is 5 and the least one bigger than the divisors is 29.
• Greatest n-digit such number: with U the greatest n-digit number, k_max = floor((U − r) ÷ L); the number is L × k_max + r.
• Smallest n-digit such number: with B the smallest n-digit number, k_min = ceil((B − r) ÷ L); the number is L × k_min + r. Do not take the smallest n-digit multiple of L and add r; it can skip a smaller valid number (L = 12, r = 9: the smallest three-digit number is 12 × 8 + 9 = 105, not 108 + 9 = 117).

Radhika wants numbers that leave remainder 7 when divided by 10, 12 and 15. L = 60.

• Least: 60 + 7 = 67.
• Greatest four-digit: k_max = floor((9999 − 7) ÷ 60) = 166, so the number is 60 × 166 + 7 = 9967.

[[fig:1]]

Other forms of the same question.

• "Which option leaves remainder r?" Subtract r from each option and test divisibility by L.
• "B = 500 − A leaves remainder 2" or "what must be subtracted from N so that the result leaves remainder r": write the result as Lk + r and choose the k that fits.
• The remainder may be described in words, such as "a remainder equal to the HCF of the divisors". Work out that number first, then proceed as usual.

Different remainders with a constant gap. A number leaves remainders 4, 7 and 13 when divided by 6, 9 and 15. The remainders are different, but now look at (divisor − remainder): 6 − 4 = 2, 9 − 7 = 2, 15 − 13 = 2. Every time, the number is 2 short of a multiple of the divisor. So (number + 2) is divisible by 6, 9 and 15.

[[fig:0]]

If divisor − remainder = d is the same for all, then Number = LCM × k − d

For 6, 9, 15: LCM = 90, so the least number = 90 − 2 = 88. Check: 88 = 14 × 6 + 4 = 9 × 9 + 7 = 5 × 15 + 13.

Such questions are built so that this gap is the same for every divisor. So before solving, subtract each remainder from its divisor and look for the common gap.

The same method works with N = L × k − d, that is, r = −d. For the greatest n-digit number, k_max = floor((U + d) ÷ L); for the smallest, k_min = ceil((B + d) ÷ L), where U and B are the greatest and smallest n-digit numbers. Then check the answer has n digits. (A multiple just above U can still give a valid answer after subtracting d.)

Same remainder plus an extra divisibility condition. "Least number that leaves remainder r with a, b, c and is divisible by m." Write the number as Lk + r and try k = 1, 2, 3, … until it is divisible by m.

To find k quickly, replace L and r by their remainders on division by m. Say Radhika wants the least number that leaves remainder 1 when divided by 2, 3 and 4, and is divisible by 7. Number = 12k + 1. 12 leaves remainder 5 on division by 7, so 5k + 1 must be a multiple of 7: k = 4 gives 21 ✓. Number = 12 × 4 + 1 = 49.

[[fig:1]]

The question then usually asks something about that number, such as the sum of its digits or its remainder when divided by another number.

Every question of this type tells the same story. Some quantities have to be cut, measured, packed or grouped into equal parts, with nothing left over, and each part has to be as big as possible.

"Nothing left over" means the part must divide every quantity, so it is a common factor. "As big as possible" means the highest such factor. That is exactly the HCF.

• Greatest length of a rod, tape or piece that measures or cuts given lengths exactly → HCF of the lengths.
• Greatest capacity of a container that measures given volumes exactly → HCF of the volumes.
• Largest square tile for a rectangular floor → HCF of the length and breadth.
• Maximum number of students in each group, where each group has students of one class only → HCF of the class sizes.
• Maximum trees in a row, where a row has one variety only → HCF of the numbers of trees.

[[fig:0]]

Units first. If lengths are given as 3 m 40 cm, 5 m and so on, convert everything into the smallest unit (cm or mm) and remove decimals. Then take the HCF, and finally convert the answer to the unit the options use.

Radhika has three ribbons of 1.2 m, 1.8 m and 2.4 m and wants to cut them into equal pieces of the greatest possible length. In cm they are 120, 180 and 240. HCF = 60 cm = 0.6 m, and she gets 2 + 3 + 4 = 9 pieces.

[[fig:1]]

In the previous type the question asked for the size of the biggest part. Here it asks the next question: how many parts, or how much in each share. Find the HCF exactly as before, and then divide.

Number of square tiles. For a floor of length L and breadth B, the largest tile has side s = HCF(L, B). Tiles along the length = Ls, along the breadth = Bs.
Number of tiles = Ls × Bs = L × Bs²
The largest tile also gives the least number of tiles, so questions on the least number of square tiles are the same question.

Number of pieces, cans or cartons. With part size h = HCF, the number of parts = ah + bh + ch. The biggest part gives the smallest number of parts.

Sharing among the maximum number of people. If a items of one kind and b items of another are to be shared equally among as many people as possible, the number of people = HCF(a, b), and each person gets aHCF of the first item and bHCF of the second.

A floor is 270 cm × 180 cm. s = HCF(270, 180) = 90 cm, so the tiles needed are 3 × 2 = 6 (see the figure). And if Radhika shares 48 pens and 72 pencils among the maximum number of friends, she can share among HCF = 24 friends, each getting 2 pens and 3 pencils.

[[fig:0]]

[[fig:1]]

One more thing to notice: aHCF and bHCF are always co-prime. That gives you a quick check on your answer.

Now the opposite story. Several things repeat at fixed intervals: bells ring every few seconds, lights change every few seconds, runners finish a round every few seconds, people visit every few days. They all start together. When will they be together again?

Each thing is back "in step with the start" at multiples of its own interval. All of them are together at the common multiples, and the first such time is the least common multiple.

They come together again after the LCM of the intervals.

[[fig:0]]

Clock time. Convert the LCM into minutes and seconds and add it to the starting time. LCM = 378 seconds = 6 min 18 s; starting at 10:15:00, they change together again at 10:21:18.

Runners on a circular track. If they start together from the same point in the same direction and take a, b, c seconds per round, they are together at the starting point after LCM(a, b, c) seconds. Here the time per round is what repeats, so the speed or the length of the track is not needed.

How many times in a period? After the start, they come together every L units of time (L = LCM). In a period T:

• Number of times, excluding the start = the whole-number part of TL
• Number of times, including the start = that number + 1

Read the question carefully for including or excluding. When it says they commence together and asks how many times they ring together in T, the ringing at the start is normally counted.

Radhika's two alarms beep every 8 minutes and every 12 minutes. LCM = 24 minutes. In 2 hours (120 minutes) they beep together 12024 = 5 times after the start, and 6 times if the start is counted.

[[fig:1]]

Days. "Every 2nd day, every 3rd day" means intervals of 2 days and 3 days. Count the days carefully from the given starting date (30 days in November, 31 in December, and so on).