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