when $a$ and $b$ are relatively primes, how is $ax - by= 1$ always possible?

Question

If $a$ and $b$ are relatively primes, with any number of $x$ and $y$, you could always find a set of $x$ and $y$ which makes $ax-by=1$

How is it possible?

Answer 1

Given $a,b$ with $\gcd(a,b)=1$, let $c$ be the smallest positive integer of the form $ax-by$. We claim $c$ divides every number of the form $ax-by$. For let $am-bn=c$ and $ax-by=d$, then by the Division Theorem $d=cq+r$ with $0\le r<c$, so $$r=d-cq=ax-by-(am-bn)q=au-bv$$ where $u=x-mq$ and $v=y-nq$; by the minimality of $c$, we must have $r=0$, so $c$ divides $d$. Then $c$ must divide $a$ (take $x=1$, $y=0$) and $c$ must divide $b$ (take $x=0$ and $y=-1$), so $c=1$, QED.