Problem 32E

Use the Euclidean algorithm to find

a) gcd(1, 5).

b) gcd(100,101).

c) gcd(123, 277).

d) gcd(1529, 14039).

e) gcd( 1529, 14038).

f) gcd( 11111, 111111).

Solution:-

Step1

Given that

We have to use the Euclidean algorithm to find gcd.

Step2

a) gcd(1, 5)

By using Euclidean algorithm

As 1 is the last nonzero remainder.

Therefore, gcd(1, 5) is 1.

Step3

b) gcd(100,101)

By using Euclidean algorithm

As 1 is the last nonzero remainder.

Therefore, gcd(100, 101) is 1.

Step4

c) gcd(123, 277)

By using Euclidean algorithm

As 1 is the last nonzero remainder.

Therefore, gcd(123, 277) is 1.

Step5

d) gcd(1529, 14039)

By using Euclidean algorithm

As 139 is the last nonzero remainder.

Therefore, gcd(1529, 14039) is 139.

Step6

e) gcd( 1529, 14038)

By using Euclidean algorithm

As 1 is the last nonzero remainder.

Therefore, gcd( 1529, 14038) is 1.

Step7

f) gcd( 11111, 111111)

By using Euclidean algorithm

As 1 is the last nonzero remainder.

Therefore, gcd( 11111, 111111) is 1.