Assume that m ≥ n. Verify that d divides m and n if and only if d divides both n and m mod n.

Step-by-step solution

Idea: Division gives m = qn + r with remainder r = m mod n, so r = m − qn. Then argue both ways, just as for gcd(m, n) = gcd(n, m − n): taking away (or adding) whole multiples of n does not change which numbers divide.

1. Divide m by n: m = qn + r, where q is the quotient and r = m mod n, with 0 ≤ r < n. So r = m − qn.½ mark
2. If d divides m and n: write m = ad and n = bd. Then r = m − qn = ad − qbd = (a − qb)d, so d divides r = m mod n. And d divides n already.1 mark
3. If d divides n and m mod n: write n = xd and r = yd. Then m = qn + r = qxd + yd = (qx + y)d, so d divides m. And d divides n already.1 mark
4. Both directions hold, so d divides m and n if and only if d divides n and m mod n. (If r = 0, every d divides 0 = 0 × d, so the statement still holds.) Example: m = 60, n = 16, r = 12: the common divisors of 60 and 16 are 1, 2, 4, and so are those of 16 and 12.½ mark

Check: m = 100, n = 36: 100 mod 36 = 28. Common divisors of 100 and 36: 1, 2, 4. Common divisors of 36 and 28: 1, 2, 4 ✓.

Answer to write in the exam

Common mistakes that cost marks

• Proving only one direction. “If and only if” needs both: (m, n) ⇒ (n, m mod n) and back.
• Writing m mod n = m − n. The remainder is m − qn, where q is the quotient (it equals m − n only when q = 1).
• Verifying with one numerical example and calling it a proof; an example only illustrates the statement.

How this can come in the exam

Try one yourself

Verify the statement for m = 75 and n = 20 by listing common divisors.

More questions like this

• Write an algorithm prime(n) to check if n is prime.
  (Hint: A prime number p has exactly two distinct factors, 1 and p. Can you make use of divisors(n) to write out prime(n)?)
• Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers.
  (Hint: Compute divisors(n) and then filter out the primes in this list.)
• We can also find the gcd of two numbers by computing prime factorisation of both the numbers. Try to write an algorithm to compute the prime factorisation of a number.
• These days the word ‘algorithm’ pops up everywhere. What exactly is an algorithm? What does it have to do with mathematics?
• Add two 4-digit numbers using the steps we have written down. Make sure you follow the steps precisely; do not perform any action that is not explicitly mentioned. Are you able to obtain the correct result?

All Algorithms questions · All maths questions