1

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$.

Community
  • 1
fibonacci
  • 23
  • I found the GCD to be $127$, but I don't know how to do it using the algorithm. – fibonacci Jan 23 '15 at 20:49
  • Is this how you do it? 128397 = 650241 + 63373 65024 = 633731 + 1651 63373 = 165138 + 635 1651 = 6352 + 381 635 = 3811 + 254 381 = 2541 + 127 254 = 127*2 + 0 – fibonacci Jan 23 '15 at 20:54
  • Okay so you found the $gcd$ to be $127$. How did you find this? By using the Euclidean algorithm right? You want to sort of reverse the process (using substitution) to obtain the linear combination you are looking for. – Daniel W. Farlow Jan 23 '15 at 20:54
  • @induktio Is my process to find the GCD okay, above? – fibonacci Jan 23 '15 at 20:55
  • Did you try working it backwards as mathtastic suggested in his answer? – Daniel W. Farlow Jan 23 '15 at 21:13
  • @induktio I am doing it right now to find the linear combination, but is my work for GCD correct as shown above? – fibonacci Jan 23 '15 at 21:15
  • See my answer below. It details how you can use your first work to come up with the linear combination you are looking for. – Daniel W. Farlow Jan 23 '15 at 21:22

2 Answers2

0

$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$

123
  • 1,708
0

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?

Daniel W. Farlow
  • 22,531