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?


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.

  • $\begingroup$ 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. $\endgroup$
    – user800956
    Jul 5 '20 at 13:56
  • 1
    $\begingroup$ 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$.... $\endgroup$ Jul 5 '20 at 23:02
  • 1
    $\begingroup$ (continued) so $1=ax-by$ for some $x,y$. $\endgroup$ Jul 5 '20 at 23:03

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.