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—
- 1. gcd(99, 2)
- 2. gcd(825, 375)
- 3. gcd(60, 16)
Step-by-step solution
Idea: Divide the larger number by the smaller. Then divide the old divisor by the remainder, and keep going. When the remainder is 0, the last divisor is the gcd. Each division is one reduction gcd(m, n) → gcd(n, m mod n).
1. gcd(99, 2)
- 2 ) 99 ( 49: 49 × 2 = 98, remainder 99 − 98 = 1. So gcd(99, 2) = gcd(2, 1).½ mark
- 1 ) 2 ( 2: 2 × 1 = 2, remainder 0. The last divisor is 1, so gcd(99, 2) = 1.½ mark
2. gcd(825, 375)
- 375 ) 825 ( 2: 2 × 375 = 750, remainder 825 − 750 = 75. So gcd(825, 375) = gcd(375, 75).½ mark
- 75 ) 375 ( 5: 5 × 75 = 375, remainder 0. The last divisor is 75, so gcd(825, 375) = 75.½ mark
3. gcd(60, 16)
- 16 ) 60 ( 3: 3 × 16 = 48, remainder 12. So gcd(60, 16) = gcd(16, 12).
12 ) 16 ( 1: 1 × 12 = 12, remainder 4. So gcd(16, 12) = gcd(12, 4).½ mark - 4 ) 12 ( 3: 3 × 4 = 12, remainder 0. The last divisor is 4, so gcd(60, 16) = 4.½ mark
Check: 60 = 4 × 15 and 16 = 4 × 4, with 15 and 4 sharing no factor, so 4 is the gcd ✓. 825 = 75 × 11 and 375 = 75 × 5 ✓.
Answer to write in the exam
1.
99 = 49 × 2 + 1 ⇒ gcd(99, 2) = gcd(2, 1)
2 = 2 × 1 + 0 ⇒ gcd(2, 1) = gcd(1, 0)
∴ gcd(99, 2) = 1
2.
825 = 2 × 375 + 75 ⇒ gcd(825, 375) = gcd(375, 75)
375 = 5 × 75 + 0 ⇒ gcd(375, 75) = gcd(75, 0)
∴ gcd(825, 375) = 75
3.
60 = 3 × 16 + 12 ⇒ gcd(60, 16) = gcd(16, 12)
16 = 1 × 12 + 4 ⇒ gcd(16, 12) = gcd(12, 4)
12 = 3 × 4 + 0 ⇒ gcd(12, 4) = gcd(4, 0)
∴ gcd(60, 16) = 4
Common mistakes that cost marks
- Taking the last remainder (0) or the last quotient (3) as the gcd. The gcd is the last divisor, the one that leaves remainder 0.
- Dividing the remainder by the dividend instead of dividing the old divisor by the remainder.
- Subtracting wrongly in a step (e.g. 825 − 750 = 85); one wrong remainder spoils every later step.
How this can come in the exam
In the long division method for gcd(96, 36), the divisions are 36 ) 96 ( 2, then 24 ) 36 ( 1, then 12 ) 24 ( 2 with remainder 0. The gcd is
- 2
- 12
- 24
- 36
Show answer
(B) 12
The divisor that leaves remainder 0 is 12, so gcd(96, 36) = 12.
Use the long division method to find gcd(126, 56).
Show answer
56 ) 126 ( 2: 112, remainder 14. 14 ) 56 ( 4: 56, remainder 0. gcd(126, 56) = 14.Try one yourself
Find gcd(135, 48) by the long division method.
Show answer
48 ) 135 ( 2: remainder 39. 39 ) 48 ( 1: remainder 9. 9 ) 39 ( 4: remainder 3. 3 ) 9 ( 3: remainder 0. gcd(135, 48) = 3.
More questions like this
- 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)?) - 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.