For each of the following pairs of numbers a and 6 calculate

For each of the following pairs of numbers a and 6, calculate gcd(a, b) and find integers r and 5 such that gcd(a, b) = ra + sb. 14 and 39 471 and 562

Solution

We use the Euclidean algorithm as follows:

(a) 39 = 14*2 + 11

14 = 11*1 + 3

11 = 3*3 + 2

3 = 2*1 + 1

2 = 1*1 + 0

hence therefore gcd(14, 39) = 1.

(b) 562 = 471*1 + 91

471 = 91*5 + 16

91 = 16*5 + 11

16 = 11*1 + 5

11 = 5*2 + 1

5 = 1*5 + 0

hence therefore gcd(562, 471) = 1.