Problem 44E

Use the extended Euclidean algorithm to express gcd(1001, 100001) as a linear combination of 1001 and 100001.

Solution :

Step 1 :

In this problem we have to express the gcd as a linear combination.

Given numbers are 1001 and 100001.

The Euclidean algorithm uses these divisions.