Writing a GCD of two numbers as a linear combination

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

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

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

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

$$\rm\begin{eqnarray}(1)\quad \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\, -\ 7&\cdot& 19 \\ \color{#940}{(2)-2\,(3)}\,\rightarrow\,(4)\quad\ \ \ \color{#C00}{3}\ &=&\, {-}2&\cdot& 141\, + 15&\cdot& 19 \\ \color{#940}{(3)-3\,(4)}\,\rightarrow\,(5)\quad \color{#C00}{{-}1}\ &=&\,\ \ \ 7&\cdot& 141\, -\color{#0A0}{ 52}&\cdot& \color{#0A0}{19} \end{eqnarray}\qquad$$

We can also say that; $a=b(q)+r$, from our equation $a=126,b=34$, $q$ being the quotient and $r$ the remainder. Hence

$$126=34(3)+24$$

Next $a=34$ and $b=24$, then

$$34=24(1)+10$$

Following the process we will find:

$$24=10(2)+4$$ $$10=4(2)+2$$ $$4=2(2)=0$$

Our GCD is the last remainder of the non-zero equation, 2. When writing as a linear combination we start from the non-zero equation. I.e.

$$10=4(2)+2$$

Making 2 the subject:

$$2=10-4(2)$$

But $24=10(2)+4$. We can write $$4=24-10(2)$$

Substituting in $2=10-4(2)$ we find

$$2=10-(24-10(2))2$$ $$2=10-24(2)+10(4)$$ $$2=10(1)+10(4)-24(2)$$ $$2=10(5)-24(2)$$

This implies that $50-48=2$ which is our GCD.