Subgroup generated by additive integers: Expressing d as an integer combination of ra + sb. $$a = 123,\ b = 321.$$
The first part of the question I'm trying to solve wants me to find $d = \gcd(a,b)$. I can quickly solve this by using the Euclidean algorithm, and $d$ is $3$.
However, the second part requires me to express $d$ as an integer combination $ra + sb$, for some integers $r$ and $s$.
Is there any way to do this other than mashing some multiples of $a$ and $b$ on a calculator and praying the difference comes out as $|3|$?
 A: The answer is YES, using the Euclidean algorithm backwards. 
For $b=321$ and $a=123$, the Euclidean algorithm yields:


*

*$b=2\cdot a+75$

*$a=1\cdot75+48$

*$75=1\cdot48+27$

*$48=1\cdot27+21$

*$27=1\cdot21+6$

*$21=3\cdot6+3$ and $3$ divides $6$


Hence the greatest common divisor of $a$ and $b$ is $d=3$. Furthermore:


*

*$d=21-3\cdot6$ by (6)

*$6=27-21$ by (5), hence $d=21-3\cdot(27-21)=4\cdot21-3\cdot27$

*$21=48-27$ by (4), hence $d=4\cdot(48-27)-3\cdot27=4\cdot48-7\cdot27$

*$27=75-48$ by (3), hence $d=4\cdot48-7\cdot(75-48)=11\cdot48-7\cdot75$ 

*$48=a-75$ by (2), hence $d=11\cdot(a-75)-7\cdot75=11\cdot a-18\cdot75$  

*$75=b-2\cdot a$ by (1), hence $d=11\cdot a-18\cdot(b-2a)=47\cdot a-18\cdot b$


Finally, $d=47a-18b$.
A: The idea is to go backward using the Euclidean Algorithm. 
Since $321$ and $123$ has a long Euclidean algorithm, I will do $23$ and $7$ instead to illustrate: 
$23 = 3(7) + 2 \ \ \ (1)$
$7 = 3(2) + 1 \ \ \ (2)$
$2 = 2(1) + 0$
So gcd(23, 7) = 1.
Now by equation (2)
$1 = 7 - 3(2) \ \ \ (*)$
By equation (1), you have
$2 = 23 - 3(7)$
Substituting into $(*)$, you get
$1 = 7 - 3(23 - 3(7)) = 7 - 3(23) + 9(7) = 10(7) - 3(23)$
So you have 
$gcd(23,7) = 1 = 10(7) - 3(23)$. 
A: The matrix Euclidean algorithm is reasonably useful to know, and reasonably easy to execute. The idea is to write down the remainders as a row vector on the right hand side of the equality.  The left hand side will be a vector-matrix multiplication. To get the next line, on the right hand side we need to shift the right column one to the left, and then the new right column is a linear combination of the old columns.  For instance 75 is one copy of 321 minus two copies of 123.  The left hand side is done the same: the left column scoots over one to the left, and the right column is a linear combination. For instance $\begin{smallmatrix}1\\-2\end{smallmatrix}$ is one copy of the left column $\begin{smallmatrix}1\\0\end{smallmatrix}$ minus two copies of the right column $\begin{smallmatrix}0\\1\end{smallmatrix}$, abbreviated as $N=L-(2)(R)$.
So in each equation below, we figure out how to fix the right hand side using the division algorithm, then we just do the same thing to the left hand side.
$$\newcommand{\matty}[6]{
\begin{bmatrix} 321 & 123 \end{bmatrix} \cdot \begin{bmatrix} #1 & #3 \\ #2 & #4 \end{bmatrix} = \begin{bmatrix} #5 & #6 \end{bmatrix}}
\matty{1}{0}{0}{1}{321}{123} \phantom{ \qquad N = L - (2)(R) }\\
\matty{0}{1}{1}{-2}{123}{75} \qquad N = L - (2)(R) \\
\matty{1}{-2}{-1}{3}{75}{48} \qquad N = L - (1)(R)\\
\matty{-1}{3}{2}{-5}{48}{27} \qquad N = L - (1)(R)\\
\matty{2}{-5}{-3}{8}{27}{21} \qquad N = L - (1)(R)\\
\matty{-3}{8}{5}{-13}{21}{ 6} \qquad N = L - (1)(R)\\
\matty{5}{-13}{-18}{47}{ 6}{ 3} \qquad N = L - (3)(R)\\
\matty{-18}{47}{41}{-107}{ 3}{ 0} \qquad N = L - (2)(R)\\
$$
This gives us the information that $$3 = (321)(-18) + (123)(47)$$ but even more, it tells us that $$0 = (321)(41) + (123)(-107)$$ so we can actually find lots of ways to get $3$:
$$3 = (321)(-18+41k) + (123)(47-107k) \text{ for any } k$$
so for instance we also get ($k=1$):
$$3 = (321)(23) + (123)(-60)$$
