GCD Using Euclidean Algorithm

Question

How do I find the GCD of $65024$ and $128397$? And how do I express the GCD as a linear combination of $65024$ and $128397$ of the form $g = a\cdot 65024 + b\cdot 128397$?

My work:

$128397 = 65024\cdot 1 + 63373$

$65024 = 63373\cdot 1 + 1651$

$63373 = 1651\cdot 38 + 635$

$1651 = 635\cdot 2 + 381$

$635 = 381\cdot 1 + 254$

$381 = 254\cdot 1 + 127$

$254 = 127\cdot 2 + 0$

Thus, the GCD is $127$.

Answer 1

The way you got the $\mathrm{gcd}$ is fine. But as people have pointed out, you want to work backward to get your answer. Consider the following: \begin{align} 127 &= 381-254\\[0.5em] &= 381-[635-381]=2\cdot 381-635\\[0.5em] &= 2[1651-2\cdot 635]-635 = 2\cdot 1651-5\cdot 635\\[0.5em] &= 2\cdot 1651-5[63373-38\cdot 1651]=192\cdot 1651-5\cdot 63373\\[0.5em] &= 192[65024-63373]-5\cdot 63373=192\cdot 65024-197\cdot 128397\\[0.5em] &= 192\cdot 65024-197[128397-65024]=389\cdot 65024-197\cdot 128397 \end{align} Thus, we have that $$ 127=389\cdot 65025+(-197)\cdot 128397. $$ This is your linear combination. So you have $g=65025a+128397b$, where $g=127,a=389,b=-197$.

Is that clear?

Answer 2

$gcd(a,b)$ with $a \ge b$:

$$a=q_0b+r_0$$ $$ b = q_1 r_0 + r_1$$ $$r0 = q_2 r_1 + r_2$$ $$r1 = q_3 r_2 + r_3$$ $$...$$

Where the last remained term $r_n=gcd(a,b)$

And for $ax+by=c$

you work your way backward through this process, substituting 'upward' until you can express $c=ax+by$