Consider the earlier example gcd(99, 2) that took a long time to converge. Here is what happens when we execute the improved algorithm.
Answer: 99 mod 2 = 1, so gcd(99, 2) → gcd(2, 1); 2 mod 1 = 0, so gcd(2, 1) → gcd(1, 0). Answer 1, in only two reduction steps.
Step-by-step solution
Given: The improved algorithm: 1. If m < n, reverse the numbers and compute gcd(n, m). 2. If n = 0, report the answer as m. 3. Otherwise, reduce the problem to computing gcd(n, m mod n), where m mod n is the remainder when m is divided by n.; With repeated subtraction (gcd(m, n) → gcd(n, m − n)), gcd(99, 2) needed about 50 reductions: gcd(97, 2), gcd(95, 2), …, gcd(1, 0).
Idea: m mod n is the remainder when m is divided by n. It is what is left after subtracting n from m as many times as possible, so one division does the work of many subtractions.
- 99 ≥ 2, so no reversal. Step 3: 99 ÷ 2 = 49 remainder 1, so 99 mod 2 = 1 → gcd(2, 1). (This one step replaces the 49 subtractions of 2.)1 mark
- Step 3: 2 ÷ 1 = 2 remainder 0, so 2 mod 1 = 0 → gcd(1, 0).½ mark
- Now n = 0, so Step 2 gives the answer 1. Only two reduction steps were needed.½ mark
gcd(99, 2) = 1, found in two reduction steps: gcd(99, 2) → gcd(2, 1) → gcd(1, 0).
Answer to write in the exam
99 mod 2 = 1 (99 = 49 × 2 + 1)
gcd(99, 2) = gcd(2, 1)
2 mod 1 = 0 (2 = 2 × 1 + 0)
gcd(2, 1) = gcd(1, 0)
∴ gcd(99, 2) = 1 (two reductions)
Common mistakes that cost marks
- Writing the quotient (49) instead of the remainder (1) as 99 mod 2.
- Writing gcd(1, 2) instead of gcd(2, 1); the divisor n moves to the first place.
- Stopping at gcd(2, 1) and guessing the answer without reaching n = 0. (The answer is the same here, but the algorithm stops only at n = 0.)
How this can come in the exam
MCQ (1 mark)
47 mod 6 =
- 1
- 5
- 7
- 41
Show answer
(B) 5
47 = 7 × 6 + 5, so the remainder is 5.
Try one yourself
Use the improved algorithm to find gcd(85, 4).
Show answer
85 mod 4 = 1 → gcd(4, 1); 4 mod 1 = 0 → gcd(1, 0). gcd(85, 4) = 1.
More questions like this
- In other words, we needed only two reduction steps to get to the final answer. Check that this would happen for any similar problem of the form gcd(2k + 1, 2).
- The above modified algorithm can be carried out concisely using the “long division” method given by Indians at least from the time of Āryabhaṭa. We illustrate the method through the following examples—
- Compute the following using the improved version of Euclid’s algorithm.
- Assume that m ≥ n. Verify that d divides m and n if and only if d divides both n and m mod n.
- 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)?)