# Euclidean Algorithm (gcd)

Show that if $a$ and $b$ are positive integers, and $d=\gcd(a,b)$ then there exists positive integers $s, t$ such that

$$d = sa − tb.$$

I'm really unsure of how to approach this. I follow the proof of how $d=sa+tb$ but I'm not sure how to change it to suit this. Any help would be much appreciated.

You know already that $d=sa+tb$ with $s,t\in \Bbb Z$. What could possibly go wrong?
If $t<0$ then certainly $s>0$ as otherwise $d=sa+tb\le tb<0$ and we are done by having $d=sa-(-t)b$.
If $t=0$ then $d$ is a multiple of $a$, which implies $d\mid b$, i.e., $b=rb$ with $r\in\Bbb N$. This gives us $d=(s+r)a-1\cdot b$.
If $t>0$, then $d=sa+tb = (s+2tb)a-(2a-1)tb$, where as in the first case necessarily $s+2tb>0$.