How to find integer linear combination [duplicate]

$\begingroup$

The question said:

Use the Euclidean Algorithm to find gcd $(1207,569)$ and write $(1207,569)$ as an integer linear combination of $1207$ and $569$

I proceeded as follows:

$$ 12007 = 569(2) +69$$

$$569 = 69(8) +17$$

$$69 = 17(4) +1$$

$$17 = 1(17) + 0$$

Thus the gcd = 1

The part I am having problems with is how calculate and write it was a linear combination. Can someone help?

$\endgroup$ 4

1 Answer

$\begingroup$

Now you need to go back in the steps. You know that $1=69-17\times 4$. From the previous step you know that $17=569-69\times 8$. Putting this to the previous equation we get:

$1=69-(569-69\times 8)\times 4$.

Finally if we take it one step back in the algorithm we get $69=1207-569\times 2$. So we get:

$1=1207-569\times 2-(569-(1207-569\times 2)\times 8)\times 4=1207\times 33+569\times (-70)$

$\endgroup$