Exercise 1.2.1 (Greater common divisor)

By using the Euclidean algorithm, find the greatest common divisor (g.c.d.) of

(a)
7469 and 2464;
(b)
2689 and 4001;
(c)
2947 and 3997;
(d)
1109 and 4999.

Answers

(a) We have

(7469,2464) = (7469 − 3 ⋅ 2464,2464) = (77,2464) = (77,2464 − 32 ⋅ 77) = (77,0) = 77

(b) We have

(2689,4001) = (2689,4001 − 2689) = (2689,1312) = (2689 − 2 ⋅ 1312,1312) = (65,1312) = (65,1312 − 20 ⋅ 65) = (65,12) = (65 − 5 ⋅ 12,12) = (5,12) = (5,12 − 2 ⋅ 5) = (5,2) = (5 − 2 ⋅ 2,2) = (1,2) = (1,2 − 2 ⋅ 1) = (1,0) = 1
User profile picture
2022-05-12 18:16
Comments