Let $a,b \in \Bbb N$ with $\gcd(a,b)=1$. Show that for every integer $n>ab$ the equation $ax+by=n$ has a solution in positive integers $x,y$. (Take $(x,y)$ with $y \leq 0$ and $x$ minimal).
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Hint $\rm\:(a,b)=1\,\Rightarrow\, \exists\, x\!:\ ax\equiv n\pmod b,\:$ so $\rm\:n = ax + by,\:$ and $\rm\:0<x\le b\:\Rightarrow y > 0,\:$ by $\rm\:n > ab.$
$$gcd(a,b)=1\Longleftrightarrow \,\exists\,x,y\in\Bbb Z\,\,s.t.\,\,ax+by=1$$
Now just multiply the above by any $\,n\in\Bbb Z\,$ ...
From the extended Euclidean algorithm we know $\exists r,r':\ ra+r'b=1$ where $r,r'$ are integers
Now assume without loss of generality that $x_0$ is the biggest non-positive solution to $ax+by=n$, then $y_0>0$. Using Benzouits Identity we know that we have a solution of the form:
$(x,y)=(x_0+sb,y_0-sa)$ so with the initial solution above if we let $s=1$ then $x_0+b>0$ (as $x_0$ is the biggest non-positive solution.)
Then consider $y_0-a$. We need to show that this is greater than 0.
Assume that it was not then:
$y_0-a\leq0$ which would give $by_0\leq ab$ but that would give $ax_0+by_0\leq ab$ (as $ax_0\leq 0$) which is a contradiction as we have that $(x_0,y_0)$ is a solution to $ax+by=n$ for $n>ab$
So we have that $y_0-a>0$ and so a solution in the strictly positive integers is $(x_0+b,y_0-a)$