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|$?

The answer is YES, using the Euclidean algorithm backwards.

For $b=321$ and $a=123$, the Euclidean algorithm yields:

1. $b=2\cdot a+75$
2. $a=1\cdot75+48$
3. $75=1\cdot48+27$
4. $48=1\cdot27+21$
5. $27=1\cdot21+6$
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$.