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

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?

## 1 Answer

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

• Thank you, but I don't think I can follow you at all. Why does au-bv have anything to do with c dividing a or b? Like you said, take x=1, y=0, then we get u=1-mq and v=-nq. Since r=0, that makes au=bv, meaning a-amq = bnq. And I'm stuck here. It's getting me nowhere. Jul 5 '20 at 13:56
• The Division Theorem says that given $c,d$ with $c>0$ you can divide $d$ by $c$ and get an integer quotient $q$ and an integer remainder $r$ with $0\le r<c$. If we let $c$ and $d$ be integers of the form $ax-by$, then the algebra that leads to $r=au-bv$ shows that $r$ is also of the form $ax-by$. If $c$ is the smallest positive integer of that form, then since $r<c$ we can't have $r$ being positive, so $r=0$, so $d$ is a multiple of $c$. So every integer of the form $ax-by$ is a multiple of $c$. So in particular, $a$ and $b$ are both multiples of $c$. But $\gcd(a,b)=1$, so $c$ must be $1$.... Jul 5 '20 at 23:02
• (continued) so $1=ax-by$ for some $x,y$. Jul 5 '20 at 23:03