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