Writing a GCD of two numbers as a linear combination

I am working on GCD's in my Algebraic Structures class. I was told to find the GCD of 34 and 126. I did so using the Euclidean Algorithm and determined that it was two. I was then asked to write it as a linear combination of 34 and 126 and I am really unsure of how to do so. I appreciate any help.

Solution 1:

Run the Euclidean algorithm "backwards". You will have already $$\eqalign{ 126&=3\times34+24\cr 34&=1\times24+10\cr 24&=2\times10+4\cr 10&=2\times4+2\ .\cr}$$ Now rewrite all these to make the remainder the subject (with practice you will find you can omit this step but it's a good thing to do initially). We get $$\eqalign{ 2&=10-2\times4\cr 4&=24-2\times10\cr 10&=34-1\times24\cr 24&=126-3\times34\ .\cr}$$ Finally substitute each remainder into the previous equation, collecting terms at each step: $$\eqalign{ 2&=10-2\times(24-2\times10)\cr &=-2\times24+5\times10\cr &=-2\times24+5\times(34-1\times24)\cr &=5\times34-7\times24\cr &=5\times34-7\times(126-3\times34)\cr &=-7\times126+26\times34\ .\cr}$$ This shows $2$ as a constant times $126$ plus a constant times $34$.

Solution 2:

Use the Extended Euclidean Algorithm to compute the Bezout identity for the gcd.

$$\begin{array}{rrr} 126 & 1 & 0\\ 34 & 0 & 1\\ 24 & 1 & -3\\ 10 & -1& 4\\ 4 & 3 & -11\\ 2 & \!\!\color{#c00}{-7} & \!\!\!\color{#0a0}{26}\end{array}\qquad$$

where each above line $\,\ a\ \ b\ \ c\ \,$ means that $\ a = 126\, b + 34\, c.\ $ Therefore

$$ 2 = -\color{#c00}{7}\cdot 126 + \color{#0a0}{26}\cdot 34\qquad$$

The linked post described the algorithm in great detail, in a way that is easy to remember.

Here is another example computing $\rm\ gcd(141,19),\,$ with the equations written explicitly

$\qquad\qquad\rm\begin{eqnarray} [\![1]\!]\ \ \ \, \color{#C00}{141}\!\ &=&\,\ \ 1&\cdot& 141\, +\ 0&\cdot& 19 \\ [\![2]\!]\quad\ \color{#C00}{19}\ &=&\,\ \ 0&\cdot& 141\, +\ 1&\cdot& 19 \\ \color{#940}{[\![1]\!]-7\,[\![2]\!]}\, \rightarrow\, [\![3]\!]\quad\ \ \ \color{#C00}{ 8}\ &=&\,\ \ 1&\cdot& 141\, \color{darkorange}{-\ 7}&\cdot& 19 \\ \color{#940}{[\![2]\!]-2\,[\![3]\!]}\,\rightarrow\,[\![4]\!]\quad\ \ \ \color{#C00}{3}\ &=& {-}2&\cdot& 141\, + \color{#90f}{15}&\cdot& 19 \\ \color{#940}{[\![3]\!]-3\,[\![4]\!]}\,\rightarrow\,[\![5]\!]\quad \color{#C00}{{-}1}\ &=&\,\ \ 7&\cdot& 141\, -\color{#0A0}{ 52}&\cdot& \color{#0A0}{19} \\ {\rm negating}\ \Rightarrow\ \ \ \ \ \ {1}\ &=& {-}7&\cdot& 141\, +\color{#0A0}{ 52}&\cdot& \color{#0A0}{19}\ \ \ \rm [Bezout\ equation] \end{eqnarray}$

The prior Bezout equation $\Rightarrow 141^{-1}\equiv \color{c00}{-7}\pmod{\!19},\,$ & $\,\color{#0a0}{19^{-1}\!\equiv 52}\pmod{\!141}\,$ by reducing the Bezout equation $\bmod19\,$ and $\bmod 141\,$ resp., as explained here. Thus we see that using the extended Euclidean algorithm to compute the gcd Bezout equation yields one method of computing modular inverses (and fractions). See here & here for more examples of this and related methods.

Equivalently $\!\bmod 141\!:\ \dfrac{0}{\color{#c00}{141}}\overset{\large\frown}\equiv\dfrac{1}{\color{#c00}{19}}\overset{\large\frown}\equiv\dfrac{\color{darkorange}{-7}}{\color{#c00}8}\equiv\dfrac{\color{#90f}{15}}{\color{#c00}{3}}\equiv\dfrac{\color{#0a0}{-52}}{\color{#c00}{-1}}\Rightarrow \color{#0a0}{19^{-1}\equiv 52},\,$ where we used a succinct fractional form of the above extended Euclidean algorithm, which boils down to viewing the above equations $\!\bmod 141.$