Answer to Question #309880 in Algebra for badshah

Question

Use the Euclidean algorithm to find the Greatest Common Divisor of:

a. 1819 and 3587 b. 42823 and 6409

Answer 1

a) Use the Euclidean algorithm to find g:

3587 = 1819 · 1 + 1768

1819 = 1768 · 1 + 51

1768 = 51 · 34 + 34

51 = 34 · 1 + 17

34 = 17 · 2 + 0

Hence the greatest common divisor is g = (3587, 1819) = 17

b) Find the gcd of 42823 and 6409.

Solution.

42823 = 6409(6) + 4369

6409 = 4369(1) + 2040

4369 = 2040(2) + 289

2040 = 289(7) + 17

289 = 17(17)

Therefore (42823, 6409) = 17