Euclid’s algorithm · 3 marks

Let us assume that m ≥ n. Then, gcd(m, n) is the same as gcd(n, m − n). Why is this the case?

Answer: Every common divisor of m and n also divides m − n, and every common divisor of n and m − n also divides m. So the two pairs have exactly the same common divisors, and therefore the same greatest one.

Step-by-step solution

Idea: Show that the two pairs (m, n) and (n, m − n) have the same set of common divisors. Then their greatest common divisors must be equal. Work in both directions.

Common divisor of m and n ⇒ divisor of m − n. Let d divide both m and n. Then m = ad and n = bd for some natural numbers a, b. So m − n = ad − bd = (a − b)d, and d divides m − n. So d is a common divisor of n and m − n.1 mark
Common divisor of n and m − n ⇒ divisor of m. Let d divide both n and m − n. Then n = xd and m − n = yd. Adding, n + (m − n) = m = xd + yd = (x + y)d, so d divides m. So d is a common divisor of m and n.1 mark
So the pairs (m, n) and (n, m − n) have exactly the same common divisors. The same set of numbers has the same largest member, so gcd(m, n) = gcd(n, m − n).½ mark
Picture: if blocks of size d exactly cover (tile) a strip of length m and a strip of length n, then cutting the n strip off the m strip leaves a strip of length m − n that is also exactly covered by blocks of size d (see the diagram). Example: 825 and 375 have common divisors 1, 3, 5, 15, 25, 75; so do 375 and 825 − 375 = 450. Both gcds are 75.½ mark

Any common divisor of m and n divides m − n, and any common divisor of n and m − n divides m. So both pairs have the same common divisors, and hence gcd(m, n) = gcd(n, m − n).

Check: m = 825, n = 375: gcd(825, 375) = 75 and gcd(375, 450) = 75 ✓.

Answer to write in the exam

Let d | m and d | n. Then m = ad, n = bd

⇒ m − n = (a − b)d, so d | (m − n)

Let d | n and d | (m − n). Then n = xd, m − n = yd

⇒ m = n + (m − n) = (x + y)d, so d | m

So (m, n) and (n, m − n) have the same common divisors.

∴ gcd(m, n) = gcd(n, m − n)

Common mistakes that cost marks

Proving only one direction (common divisors of m and n divide m − n) and stopping. Both directions are needed to show the two sets are the same.
Checking one example and calling it a proof. An example shows the idea; the algebra with d proves it for all numbers.
Writing m − n = (a + b)d. Subtracting gives (a − b)d.

How this can come in the exam

Assertion–Reason (1 mark)

Assertion (A): gcd(144, 60) = gcd(60, 84).
Reason (R): For m ≥ n, the pairs (m, n) and (n, m − n) have exactly the same common divisors.

Both A and R are true, and R is the correct explanation of A.
Both A and R are true, but R is not the correct explanation of A.
A is true but R is false.
A is false but R is true.

Show answer

(A) Both A and R are true, and R is the correct explanation of A.
144 − 60 = 84, so by R the two pairs have the same common divisors and hence the same gcd (both are 12). R explains A.

Try one yourself

Without finding any gcd, explain why gcd(119, 51) = gcd(51, 68).