Euclidean Algorithm Question So I have been asked to find $d=(a,b)$ when $a=1109$ and $b=4999$ and express $d$ as a linear combination of $a$ and $b$

Well I have worked out that $d=1$ but I am struggling to express $d$ as a linear combination of $a$ and $b$

$4999=1109*4+563$
$1109=1*563+546$
$563=1*546+17$
$546=17*32+2$
$17=2*8+1$
$2=2*1$

then i have $d=1$
to work out $d$ as a linear combination i have 
$563=4999-4*1109$
$546=1109-1*563$
 $546=1109-1(4999-1109*4)$
 $546=5*1109-4999$
$17=563-546$
$17=4999-4*1109-1109-563$
$17=4999-4*1109-1109+4999-4*1109$
$17=2*4999-9*1109$
$2=546-17*32$
$2=...$
$2=-65*4999+293*1109$
$1=17-8*2$
$1=...$
$1=522*4999-2353*1109$

What I need to know is how do I work out $2=-65*4999+293*1109$ and $1=522*4999-2353*1109$ without pages of working out? also is what i have done trying to express $d$ as a linear combination of $a$ and $b$ correct? Is there a quicker way of working it out?

Many thanks for your help
http://en.wikipedia.org/wiki/Continued_fraction#Finite_continued_fractions  

The cross product of consecutive convergents in simple continued fractions are either $\pm 1.$ The first in the string is always  $\frac{0}{1}.$ The second in the string is always the nonsensical $\frac{1}{0}.$ The convergents for $\frac{4999}{1109}$ are
$$ \frac{0}{1}, \; \frac{1}{0}, \; \frac{4}{1}, \; \frac{5}{1}, \;  \frac{9}{2}, \;   \frac{293}{65}, \;  \frac{2353}{522}, \; \frac{4999}{1109}.$$

We get little 2 by 2 determinant $$ 2353 \cdot 1109 - 522 \cdot 4999 = -1.   $$

So $$ -2353 \cdot 1109 + 522 \cdot 4999 = 1.   $$

This is not a difficult method to learn and has other uses. Note that the letters $a_i,$ called quotients on wikipedia, are $$ \langle 4; 1,1,32,8,2 \rangle. $$
These are $ \langle a_0; a_1,a_2,a_3,a_4,a_5 \rangle. $ I did it with a calculator. Beginning with the number $x_0 = \frac{4999}{1109} \approx 4.5077664563,$ we begin with $$ a_0 = \lfloor x_0 \rfloor = 4.$$ The fractional part is $x_0 - \lfloor x_0 \rfloor \approx 0.5077664563,$ and we take the reciprocal to get 
$$ x_1 = \frac{1}{x_0 - \lfloor x_0 \rfloor} \approx  \frac{1}{0.5077664563} \approx 1.969804617  $$ 

Then $$ a_1 = \lfloor x_1 \rfloor = 1.$$ The fractional part is $x_1 - \lfloor x_1 \rfloor \approx 0.969804617,$ and we take the reciprocal to get 
$$ x_2 = \frac{1}{x_1 - \lfloor x_1 \rfloor} \approx  \frac{1}{0.969804617} \approx 1.031135532.  $$ 

Then $$ a_2 = \lfloor x_2 \rfloor = 1.$$ The fractional part is $x_2 - \lfloor x_2 \rfloor \approx 0.031135532,$ and we take the reciprocal to get 
$$ x_3 = \frac{1}{x_2 - \lfloor x_2 \rfloor} \approx  \frac{1}{0.031135532} \approx 32.11764617.  $$ 

Then $$ a_3 = \lfloor x_3 \rfloor = 32.$$ The fractional part is $x_3 - \lfloor x_3 \rfloor \approx 0.11764617,$ and we take the reciprocal to get 
$$ x_4 = \frac{1}{x_3 - \lfloor x_3 \rfloor} \approx  \frac{1}{0.11764617} \approx 8.500064218.  $$

Then $$ a_4 = \lfloor x_4 \rfloor = 8.$$ The fractional part is $x_4 - \lfloor x_4 \rfloor \approx 0.500064218,$ and we take the reciprocal to get 
$$ x_5 = \frac{1}{x_4 - \lfloor x_4 \rfloor} \approx  \frac{1}{0.500064218} \approx 1.999743161.  $$ it is here that experience becomes critically important. We are seeing the effect of tiny calculator roundoffs. The actual value is $x_5 = 2,$ from which we get $a_5 = 2,$ and that concludes the s.c.f. 

Let us put in the "quotients" where they belong in the calculation:
$$ \frac{0}{1}, \; \frac{1}{0}, \; \color{magenta}{\frac{4}{}}, \; \frac{4}{1}, \; \color{magenta}{\frac{1}{}}, \; \frac{5}{1}, \; \color{magenta}{\frac{1}{}}, \; \frac{9}{2}, \; \color{magenta}{\frac{32}{}}, \;  \frac{293}{65}, \; \color{magenta}{\frac{8}{}}, \; \frac{2353}{522}, \; \color{magenta}{\frac{2}{}}, \;\frac{4999}{1109}.$$

In every case, given two consecutive numerators (in black) followed by a quotient (in magenta), the first numerator plus the second numerator times the quotient is the following numerator. So, $$ 0 + 1 \cdot 4 = 4, \;  1 + 4 \cdot 1 = 5, \;  4 + 5 \cdot 1 = 9, \;  5 + 9 \cdot 32 = 293, \;  9 + 293 \cdot 8 = 2353, \;  293 + 2353 \cdot 2 = 4999.  $$ 

Same for denominators, $$ 1 + 0 \cdot 4 = 1, \;  0 + 1 \cdot 1 = 1, \;  1 + 1 \cdot 1 = 2, \;  1 + 2 \cdot 32 = 65, \;  2 + 65 \cdot 8 = 522, \;  65 + 522 \cdot 2 = 1109.  $$ 

In case you are worried by this: the exact version, with fractions instead of calculator decimal approximations, is exactly what you have been doing:
$$  x_0 = \frac{4999}{1109} = 4 + \frac{563}{1109},  $$
$$  x_1 = \frac{1109}{563} = 1 + \frac{546}{563},  $$
$$  x_2 = \frac{563}{546} = 1 + \frac{17}{546},  $$
$$  x_3 = \frac{546}{17} = 32 + \frac{2}{17},  $$
$$  x_4 = \frac{17}{2} = 8 + \frac{1}{2},  $$
$$  x_5 = \frac{2}{1} = 2.  $$
Write down the quotients backwards
8  32  1  1  4, leaving out the last quotient 8.
Then write
   8   32   1   1   4
1  8
Then multiply the first 32 in the top row by the 8 in the bottom row and add the 1 in the second row, getting 257, and write
   8   32    1   1   4
1  8   257
Then multiply the first 1 in the first row by the 257 in the second row and add the 8 in the second row, getting 265, and write
   8   32    1    1    4
1  8  257  265
Multiply the second 1 in the first row by the 265 and add 257, getting 522, and write
   8    32    1     1    4 
1  8   257  265   522
Finally, multiply the 4 in the first row by 522 and add 265, getting 2353, and write
   8    32    1     1      4
1  8   257  265   522   2353
Now write a - sign under the 8 in the second row, a + under the 257, etc, getting
   8    32    1     1     4
1  8   257  265   522  2353
   -    +    -     +     -
Finally, write x under the 2353 and y under the 522, the result of which is 
x = -2253, y - 522, and we have solved 1109x + 4999y = 1.

Art DuPre'