Use Euclids algorithm to find the Greatest Common Divisor fo

Use Euclid\'s algorithm to find the Greatest Common Divisor for each of the following. 5280 and 3600 19201 and 3587

Solution

Formal description of the Euclidean algorithm

a) 5280, 3600

here first one greater than second one .

Divide 5280 by 3600, and get the result 1 and Remainder = 1680, so 5280 = 1*3600 + 1680

Remainder is not zero so algorithm continues,

Divide 3600 by 1680, and get the result 2 and Remainder = 240., So 3600 = 2*1680 + 240

Divide 1680 by 240, and get the result 7 and here Remainder = 0 So 1680 = 7*240 + 0

So as remainder is zero we can stop here and GCD is 240 by the algorithm.

Greatest Common Divisor of 5280 and 3600 is 240.

b) solution:

19201 and 3587

Divide 19201 by 3587, and get the result 5 and Remainder = 1266, so 19201 = 5*3587 + 1266

Remainder is not zero so algorithm continues,

Divide 3587 by 1266, and get the result 2 and Remainder = 1055., So 3587 = 2*1266 + 1055

Divide 1266 by 1055, and get the result  1 and here Remainder = 211, So 1266 = 1*1055 + 211

Divide 1055 by 211, and get the result  5 and here Remainder = 0, So 1055 = 5*211 + 0

So as remainder is zero we can stop here and GCD is 211 by the algorithm.

Greatest Common Divisor of 19201 and 3587 is 211.