Learnify Academy is a tuition centre in Bahrain. Classes are for students in Bahrain only.Tuition classes in Bahrain only

Euclid’s algorithm · 5 marks

Compute the following using the improved version of Euclid’s algorithm.

  1. (i) gcd(375, 825)
  2. (ii) gcd(51000, 81000)
  3. (iii) gcd(1789287, 237656)
  4. (iv) gcd(2587392, 157656)
Answer: (i) 75 (ii) 3000 (iii) 1 (iv) 24

Step-by-step solution

Given: Improved (division) version: 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.

Idea: The improved version replaces repeated subtraction by one division: gcd(m, n) = gcd(n, m mod n). Keep dividing the previous divisor by the remainder until the remainder is 0; the last divisor is the gcd.

(i) gcd(375, 825)

  1. 375 < 825, so Step 1 reverses the numbers: gcd(375, 825) = gcd(825, 375).
  2. 825 mod 375 = 75 (825 = 2 × 375 + 75) → gcd(375, 75)½ mark
  3. 375 mod 75 = 0 (375 = 5 × 75 + 0) → gcd(75, 0)½ mark
  4. The second number is now 0, so Step 2 reports the answer: gcd(375, 825) = 75 (2 reductions).
gcd(375, 825) = 75

(ii) gcd(51000, 81000)

  1. 51000 < 81000, so Step 1 reverses the numbers: gcd(51000, 81000) = gcd(81000, 51000).
  2. 81000 mod 51000 = 30000 (81000 = 1 × 51000 + 30000) → gcd(51000, 30000)
    51000 mod 30000 = 21000 (51000 = 1 × 30000 + 21000) → gcd(30000, 21000)
    30000 mod 21000 = 9000 (30000 = 1 × 21000 + 9000) → gcd(21000, 9000)½ mark
  3. 21000 mod 9000 = 3000 (21000 = 2 × 9000 + 3000) → gcd(9000, 3000)
    9000 mod 3000 = 0 (9000 = 3 × 3000 + 0) → gcd(3000, 0)½ mark
  4. The second number is now 0, so Step 2 reports the answer: gcd(51000, 81000) = 3000 (5 reductions).
gcd(51000, 81000) = 3000

(iii) gcd(1789287, 237656)

  1. 1789287 mod 237656 = 125695 (1789287 = 7 × 237656 + 125695) → gcd(237656, 125695)
    237656 mod 125695 = 111961 (237656 = 1 × 125695 + 111961) → gcd(125695, 111961)
    125695 mod 111961 = 13734 (125695 = 1 × 111961 + 13734) → gcd(111961, 13734)
    111961 mod 13734 = 2089 (111961 = 8 × 13734 + 2089) → gcd(13734, 2089)
    13734 mod 2089 = 1200 (13734 = 6 × 2089 + 1200) → gcd(2089, 1200)½ mark
  2. 2089 mod 1200 = 889 (2089 = 1 × 1200 + 889) → gcd(1200, 889)
    1200 mod 889 = 311 (1200 = 1 × 889 + 311) → gcd(889, 311)
    889 mod 311 = 267 (889 = 2 × 311 + 267) → gcd(311, 267)
    311 mod 267 = 44 (311 = 1 × 267 + 44) → gcd(267, 44)
    267 mod 44 = 3 (267 = 6 × 44 + 3) → gcd(44, 3)½ mark
  3. 44 mod 3 = 2 (44 = 14 × 3 + 2) → gcd(3, 2)
    3 mod 2 = 1 (3 = 1 × 2 + 1) → gcd(2, 1)
    2 mod 1 = 0 (2 = 2 × 1 + 0) → gcd(1, 0)½ mark
  4. The second number is now 0, so Step 2 reports the answer: gcd(1789287, 237656) = 1 (13 reductions).
gcd(1789287, 237656) = 1

(iv) gcd(2587392, 157656)

  1. 2587392 mod 157656 = 64896 (2587392 = 16 × 157656 + 64896) → gcd(157656, 64896)
    157656 mod 64896 = 27864 (157656 = 2 × 64896 + 27864) → gcd(64896, 27864)
    64896 mod 27864 = 9168 (64896 = 2 × 27864 + 9168) → gcd(27864, 9168)½ mark
  2. 27864 mod 9168 = 360 (27864 = 3 × 9168 + 360) → gcd(9168, 360)
    9168 mod 360 = 168 (9168 = 25 × 360 + 168) → gcd(360, 168)
    360 mod 168 = 24 (360 = 2 × 168 + 24) → gcd(168, 24)½ mark
  3. 168 mod 24 = 0 (168 = 7 × 24 + 0) → gcd(24, 0)½ mark
  4. The second number is now 0, so Step 2 reports the answer: gcd(2587392, 157656) = 24 (7 reductions).
gcd(2587392, 157656) = 24
(i) gcd(375, 825) = 75 (ii) gcd(51000, 81000) = 3000 (iii) gcd(1789287, 237656) = 1 (iv) gcd(2587392, 157656) = 24

Check: (ii) 51000 = 3000 × 17 and 81000 = 3000 × 27; 17 and 27 share no factor ✓. (iii) 1789287 = 3 × 19 × 31391 is odd and not divisible by 61 or 487, while 237656 = 23 × 61 × 487, so they share no prime factor ✓. (iv) 2587392 = 28 × 32 × 1123 and 157656 = 23 × 3 × 6569, so the gcd is 23 × 3 = 24 ✓.

Answer to write in the exam

(i)

gcd(375, 825) = gcd(825, 375) (375 < 825)

825 = 2 × 375 + 75 ⇒ gcd(825, 375) = gcd(375, 75)

375 = 5 × 75 + 0 ⇒ gcd(375, 75) = gcd(75, 0)

∴ gcd(375, 825) = 75

(ii)

gcd(51000, 81000) = gcd(81000, 51000) (51000 < 81000)

81000 = 1 × 51000 + 30000 ⇒ gcd(81000, 51000) = gcd(51000, 30000)

51000 = 1 × 30000 + 21000 ⇒ gcd(51000, 30000) = gcd(30000, 21000)

30000 = 1 × 21000 + 9000 ⇒ gcd(30000, 21000) = gcd(21000, 9000)

21000 = 2 × 9000 + 3000 ⇒ gcd(21000, 9000) = gcd(9000, 3000)

9000 = 3 × 3000 + 0 ⇒ gcd(9000, 3000) = gcd(3000, 0)

∴ gcd(51000, 81000) = 3000

(iii)

1789287 = 7 × 237656 + 125695 ⇒ gcd(1789287, 237656) = gcd(237656, 125695)

237656 = 1 × 125695 + 111961 ⇒ gcd(237656, 125695) = gcd(125695, 111961)

125695 = 1 × 111961 + 13734 ⇒ gcd(125695, 111961) = gcd(111961, 13734)

111961 = 8 × 13734 + 2089 ⇒ gcd(111961, 13734) = gcd(13734, 2089)

13734 = 6 × 2089 + 1200 ⇒ gcd(13734, 2089) = gcd(2089, 1200)

2089 = 1 × 1200 + 889 ⇒ gcd(2089, 1200) = gcd(1200, 889)

1200 = 1 × 889 + 311 ⇒ gcd(1200, 889) = gcd(889, 311)

889 = 2 × 311 + 267 ⇒ gcd(889, 311) = gcd(311, 267)

311 = 1 × 267 + 44 ⇒ gcd(311, 267) = gcd(267, 44)

267 = 6 × 44 + 3 ⇒ gcd(267, 44) = gcd(44, 3)

44 = 14 × 3 + 2 ⇒ gcd(44, 3) = gcd(3, 2)

3 = 1 × 2 + 1 ⇒ gcd(3, 2) = gcd(2, 1)

2 = 2 × 1 + 0 ⇒ gcd(2, 1) = gcd(1, 0)

∴ gcd(1789287, 237656) = 1

(iv)

2587392 = 16 × 157656 + 64896 ⇒ gcd(2587392, 157656) = gcd(157656, 64896)

157656 = 2 × 64896 + 27864 ⇒ gcd(157656, 64896) = gcd(64896, 27864)

64896 = 2 × 27864 + 9168 ⇒ gcd(64896, 27864) = gcd(27864, 9168)

27864 = 3 × 9168 + 360 ⇒ gcd(27864, 9168) = gcd(9168, 360)

9168 = 25 × 360 + 168 ⇒ gcd(9168, 360) = gcd(360, 168)

360 = 2 × 168 + 24 ⇒ gcd(360, 168) = gcd(168, 24)

168 = 7 × 24 + 0 ⇒ gcd(168, 24) = gcd(24, 0)

∴ gcd(2587392, 157656) = 24

Common mistakes that cost marks

  • Using the subtraction version (gcd(n, m − n)). The question asks for the improved version, which uses the remainder m mod n.
  • Writing the quotient instead of the remainder in the next pair (for example gcd(237656, 7) instead of gcd(237656, 125695) in (iii)).
  • Arithmetic slips in long divisions with big numbers; check each line by multiplying back: q × n + r must equal m.

How this can come in the exam

MCQ (1 mark)

Using the improved version of Euclid’s algorithm, gcd(1071, 462) is

  1. 7
  2. 21
  3. 42
  4. 231
Show answer

(B) 21
1071 = 2 × 462 + 147; 462 = 3 × 147 + 21; 147 = 7 × 21 + 0. So gcd = 21.

Short answer (2 marks)

Find gcd(4052, 12576) using the improved version of Euclid’s algorithm.

Show answer12576 = 3 × 4052 + 420; 4052 = 9 × 420 + 272; 420 = 1 × 272 + 148; 272 = 1 × 148 + 124; 148 = 1 × 124 + 24; 124 = 5 × 24 + 4; 24 = 6 × 4 + 0. gcd = 4.

Try one yourself

Find gcd(2048, 1536) and gcd(7469, 2387) using the improved version of Euclid’s algorithm.

Show answer

2048 = 1 × 1536 + 512; 1536 = 3 × 512 + 0, so gcd = 512. 7469 = 3 × 2387 + 308; 2387 = 7 × 308 + 231; 308 = 1 × 231 + 77; 231 = 3 × 77 + 0, so gcd = 77.

More questions like this

All Algorithms questions · All maths questions

← The above modified algorithm can be carried out concisely using the “lAssume that m ≥ n. Verify that d divides m and n if and only if d divi →