Find $s,t$ such that $\gcd(509,1177) = 509s+1177t$? How to find $s,t\in\mathbb{Z}$ such that $\gcd(509,1177) = 509s+1177t$?
I know that $509$ is prime and that $1177=107\cdot 11$ so we have $\gcd(509,1177)=1$. How can I proceed from here? Kind of system of equations in two variables but only one equation.
Actually I can do:
$$\begin{align*}
1177&=509 \cdot 2 + 159\\
509&=159 \cdot 3 + 32\\
159&=32 \cdot 4 + 31\\
32&=31 \cdot 1 + 1\\
31&=1 \cdot 31 + 0\\
\end{align*}$$
But not sure how to get from here that
$$1 = 37\cdot 509-16\cdot 1177$$
 A: $$  \gcd( 1177, 509 ) = ???    $$
I prefer, for the "extended" part, writing it as a continued fraction, rather than "back substitution." The reason this is possible is that the cross product of consecutive convergents is always $\pm 1$
$$ \frac{ 1177 }{ 509 } = 2 +  \frac{ 159 }{ 509 } $$
$$ \frac{ 509 }{ 159 } = 3 +  \frac{ 32 }{ 159 } $$
$$ \frac{ 159 }{ 32 } = 4 +  \frac{ 31 }{ 32 } $$
$$ \frac{ 32 }{ 31 } = 1 +  \frac{ 1 }{ 31 } $$
$$ \frac{ 31 }{ 1 } = 31 +  \frac{ 0 }{ 1 } $$
Simple continued fraction tableau:
$$ 
 \begin{array}{cccccccccccc}
 & & 2 & & 3 & & 4 & & 1 & & 31 & \\ 
  \frac{ 0 }{ 1 }   &   \frac{ 1 }{ 0 }   & &   \frac{ 2 }{ 1 }   & &   \frac{ 7 }{ 3 }   & &   \frac{ 30 }{ 13 }   & &   \frac{ 37 }{ 16 }   & &   \frac{ 1177 }{ 509 }  
 \end{array}
 $$
$$  $$
$$ 1177 \cdot 16 - 509 \cdot 37 = -1 $$
A: $$\begin{align*}1&=509s+1177t
\\&=509(s+2t)+159t
\\&=32(s+2t)+159(3s+7t)
\\&=32(s+2t)+32(15s+35t)-(3s+7t)
\\&=32(16s+37t)-(3s+7t)
\end{align*}$$
Solving for $(16s+37t)=1$ and $(3s+7t)=31$ we get $s=-1140$ and $t=493$ as one solution.

The general solution can be given as $$s=-1140+1177k$$ $$t=493-509k$$
A: Alternative approach:
Math same as the other answers, just much more kludgy (no elegance).
$1 = 32 - 31$ 
$= 32 - [159 - (4 \times 32)] = (5 \times 32) - 159$.
The line above is based on the fact that
$31 = 159 - (4 \times 32)$, which is deducible directly from one of the intermediate steps in the original poster's question.
Continuing in the same manner:
$(5 \times 32) - 159$ 
$= [5 \times (509 - 3 \times 159)] - 159
 = (5 \times 509) - (16 \times 159)$ 
$= (5 \times 509) - [16 \times (1177 - 2 \times 509)]
 = (37 \times 509) - (16 \times 1177).$
