Stuck with extended Euclidean algorithm.

Question

Use the Euclidean algorithm to express $\text{gcd}(330, 156)$ as a linear combination of $330$ and $156$.

My working so far is as follows:

$330 = 2\times156 +18$

$156= 8\times18+12$

$18=1\times12+6$

$12=2\times6+0$

therefore, $\text{gcd}(330,156) =6$.

Rearranging the equations

$18= 330-156\times2$

$12=156-8\times18$

$6=18-1\times12$

$0=12-2\times6$

I have tried to utilise the back substitution method but truth be told, finding myself totally lost and confused by it; not to mention making numerous errors.

Answer 1

Just keep expressing the remainders as expressions involving the other numbers in your algorithm steps. So \begin{align} 6&=18-12\cdot 1\\ &=18-(156-8\cdot18)\cdot1\\ &=9\cdot 18-156\\ &=9\cdot(330-2\cdot156)-156\\ &=9\cdot330-19\cdot156. \end{align}

So, in the equation $330x+156y=6$; we have $x=9$ and $y=-19$.

Answer 2

I like to write these as continued fractions, rather than "back-substitution"

$$ \gcd( 330, 156 ) = ??? $$

$$ \frac{ 330 }{ 156 } = 2 + \frac{ 18 }{ 156 } $$ $$ \frac{ 156 }{ 18 } = 8 + \frac{ 12 }{ 18 } $$ $$ \frac{ 18 }{ 12 } = 1 + \frac{ 6 }{ 12 } $$ $$ \frac{ 12 }{ 6 } = 2 + \frac{ 0 }{ 6 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 2 & & 8 & & 1 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 17 }{ 8 } & & \frac{ 19 }{ 9 } & & \frac{ 55 }{ 26 } \end{array} $$ $$ $$ $$ 55 \cdot 9 - 26 \cdot 19 = 1 $$

$$ \gcd( 330, 156 ) = 6 $$
$$ 330 \cdot 9 - 156 \cdot 19 = 6 $$