<s>[INST] 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$$
 [/INST] $$  \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 $$
</s>