2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.