Euclid’s algorithm for gcd(m, n): 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 compute gcd(n, m − n). Let us apply this algorithm to gcd(375, 825), the problem that we saw before.

Step-by-step solution

Idea: Each subtraction replaces the pair by a smaller pair with the same gcd, because gcd(m, n) = gcd(n, m − n). Keep the larger number first, and stop when the second number becomes 0.

1. 375 < 825, so Step 1: reverse → gcd(825, 375).
   Step 3: 825 − 375 = 450 → gcd(375, 450).½ mark
2. 375 < 450, so reverse → gcd(450, 375).
   Step 3: 450 − 375 = 75 → gcd(375, 75).½ mark
3. Step 3: 375 − 75 = 300 → gcd(75, 300). Reverse → gcd(300, 75).
   Step 3: 300 − 75 = 225 → gcd(75, 225). Reverse → gcd(225, 75).½ mark
4. Step 3: 225 − 75 = 150 → gcd(75, 150). Reverse → gcd(150, 75).
   Step 3: 150 − 75 = 75 → gcd(75, 75).½ mark
5. Step 3: 75 − 75 = 0 → gcd(75, 0).½ mark
6. Now n = 0, so Step 2 gives the answer 75. Step 3 (the reduction) was used 7 times.½ mark

Check: The list method gives the same: common divisors of 375 and 825 are 1, 3, 5, 15, 25, 75, so the gcd is 75 ✓.

Answer to write in the exam

Common mistakes that cost marks

• Subtracting the larger number from the smaller (375 − 825) instead of reversing first.
• Stopping at gcd(75, 75) without the last step; the rule says stop only when the second number is 0 (the answer is the same, 75, but the steps are incomplete).
• Writing gcd(n, m − n) with the numbers in the wrong places, e.g. gcd(450, 825).

How this can come in the exam

Try one yourself

Use Euclid’s subtraction algorithm to find gcd(48, 18).

More questions like this

• Are we close to our original goal of finding an algorithm where the effort is proportional to the number of digits?
• Consider the earlier example gcd(99, 2) that took a long time to converge. Here is what happens when we execute the improved algorithm.
• 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.

All Algorithms questions · All maths questions