Describe an algorithm to compute the least common multiple (lcm) of two numbers.

Step-by-step solution

Idea: The lcm is the smallest number that is a multiple of both. Every common multiple is a multiple of the larger number, so test the multiples of the larger number from the smallest upward and stop at the first one the smaller number divides.

1. Algorithm lcm(m, n)
   1. Let big = max(m, n) and small = min(m, n).
   2. For each k in the sequence 1, 2, 3, …, small:
     – if small divides k × big, report k × big as lcm(m, n) and stop.1½ marks
2. Why it is correct: the numbers k × big are exactly the multiples of big, checked from smallest to largest. The first one that small divides is a multiple of both numbers, and no smaller common multiple was skipped, so it is the least common multiple.½ mark
3. Why it always stops: when k = small, k × big = m × n, which both numbers divide. So the algorithm stops at the latest at k = small.½ mark
4. Example: lcm(12, 18). big = 18, small = 12. k = 1: 18, 12 does not divide it. k = 2: 36, 12 divides it (36 = 3 × 12). Report lcm(12, 18) = 36.½ mark
5. Another way (using the gcd algorithm): lcm(m, n) = (m × n) ÷ gcd(m, n). For 12 and 18: 216 ÷ 6 = 36, the same answer.

Check: 36 ÷ 12 = 3 and 36 ÷ 18 = 2, and the only smaller multiple of 18 is 18, which 12 does not divide ✓. Also 12 × 18 ÷ gcd(12, 18) = 216 ÷ 6 = 36 ✓.

Answer to write in the exam

Common mistakes that cost marks

• Reporting m × n as the lcm. It is a common multiple but not always the least (12 × 18 = 216, but the lcm is 36).
• Checking multiples of the smaller number against the larger one but starting the count wrongly, so a smaller common multiple is skipped.
• Mixing up lcm and gcd: the lcm is at least as big as the larger number; the gcd is at most the smaller number.

How this can come in the exam

Try one yourself

Use the algorithm to find lcm(14, 21).

More questions like this

• Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6).
• Let us keep track of a quantity called most-recent-common-divisor. We know that 1 is always a common divisor, so we can start with most-recent-common-divisor set to 1. We then scan all numbers from 2 to min(m, n). For each k from 2 to min(m, n), if k divides both m and n, update most-recent-common-divisor to k. Example: Let m = 6, n = 12.
• How would our original algorithm change if we computed the divisors of n by examining the numbers from 1 to n in reverse order, from n down to 1?
• What about the last algorithm described above? What happens when we look at common divisors starting from min(m, n) and work backwards to 1?
• Let us assume that m ≥ n. Then, gcd(m, n) is the same as gcd(n, m − n). Why is this the case?

All Algorithms questions · All maths questions