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

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.

Step 2 :

From equation (3)

From equation (2)

Thus equation (3) become