# Number Theory Problem $ax+by=n$ for $n>ab$

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

-
I assume you have learned about Bézout's lemma? So there are solutions to the equation, perhaps not with positive $x$ and $y$. The solution is not unique. So you take the hint at the end of the problem statement and work with it. What happens now? – Harald Hanche-Olsen Oct 18 '12 at 19:07

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

-
But the positivity of $x$ and $y$ …? – Harald Hanche-Olsen Oct 18 '12 at 19:08
Someone downvoted? This answer is a good hint, because it suggests that you start with arbitrary integer solution, and then work from there to find a "both positive" solution – Thomas Andrews Oct 18 '12 at 19:37
I don’t downvote, but I think that it’s a bit too skimpy to be a useful hint: it doesn’t suggest how to work from an arbitrary solution to a positive one, or even really that one can. (The hint that was apparently given with the problem, on the other hand, does.) – Brian M. Scott Oct 18 '12 at 20:52

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

-