Euclidean Algorithm help! (A) Use the Euclidean Algorithm to find $\gcd (57, 139)$.
(B) Use your work from part (a) to write your gcd as a linear combination of the two numbers.
(C) Find the inverse of $57$ in $U(139)$.
I know the gcd is $1$ and can do part (A) fine. I know I am supposed to "work backwards," but keep getting confused.
Thank you in advance!
 A: You have the extended Euclidean algorithm to obtain directly the answer:
$$ \begin{array}[t]{r@{}>{{}}l@{\qquad}rrr}
\text{Successive Divisions}&& r_i & u_i & v_i & q_i\\
     \hline
  & & 139 & 0 & 1 & \\
139 & = {\color{red}2} × 57 +\color{blue}{25} & 57 & 1 & 0 & \color{red}{2} \\
\hline
   57 & = {\color{red}2} \times {\color{blue}{25}} + \color{blue}{7} & 25 & -2 & 1 & \color{red}2 \\
  25 & = {\color{red}3} × \color{blue}{7}+\color{blue}{4} & 7 & 5 &-2 & \color{red}3 \\
  7 & = {\color{red}1} × \color{blue}{4}+\color{blue}{3} & 4 & -17 &7 & \color{red}1\\
  4 & = {\color{red}1} × \color{blue}{3}+\color{blue}{1} & 3 & 22 &-9 & \color{red}1\\
&&1 &-39&16\\
     \hline
    \end{array}$$
Thus $\;1=-39\times57+16\times139$ and $\;57^{-1}=-39\equiv \color{red}{100}\mod 139$.
A: Let's try forward, then:
$$\begin{matrix}139-2\cdot57&=\color{green}{25},\\
57-2\cdot25&=\color{green}{7}&=57-2\cdot(139-2\cdot57)&=-2\cdot139+5\cdot57,\\
25-3\cdot7&=\color{green}{4}&=(139-2\cdot57)-3\cdot(-2\cdot139+5\cdot57)&=7\cdot139-17\cdot57,\\
7-4&=\color{green}{3}&=(-2\cdot139+5\cdot57)-(7\cdot139-17\cdot57)&=-9\cdot139+22\cdot57,\\
4-3&=\color{green}{1}&=(7\cdot139-17\cdot57)-(-9\cdot139+22\cdot57)&=16\cdot139-39\cdot57.\end{matrix}$$
A: I like to work forwards. Let $a=139,b=57.$
$139=2(57)+(25)\implies25=139-2(57)=a-2b$
$57=2(25)+(7)\implies7=57-2(25)=b-2(a-2b)=5b-2a$
$25=4(7)-3\implies3=4(7)-25=4(5b-2a)-(a-2b)=22b-9a$
$7=2(3)+(1)\implies1=7-2(3)=(5b-2a)-2(22b-9a)=16a-39b$
So $1\equiv-39\cdot57\equiv18\cdot57\pmod{130}.$
