a Use the Euclidean algorithm to find gcd1001 1331 b Express

(a) Use the Euclidean algorithm to find gcd(1001, 1331).
(b) Express the gcd(1001, 1331) as a linear combination of 1001 and 1331.

a=1331

b=1001

Divide 1331 by 1001, and get the result 1 with remainder 330, so 1331= 1*1001+330

Divide 1001 by 330, and get the result 3 with remainder 11, so 1001= 3*330+11

Divide 330 by 11, and get the result 30 with remainder 0, so 330= 30*11+0

so GCD is 11.

______________________________________________________________________

now use euclidean algo backward

11=1001-3*330

11=1001-3*(1331-1*1001)

11=1001-3*1331+3*1001

11 = 4*1001-3*1331