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).
Number Theory Problem $ax+by=n$ for n>ab
-
0I assume you have learned about [Bézout's lemma](http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity)? 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? – 2012-10-18
3 Answers
Hint $\rm\:(a,b)=1\,\Rightarrow\, \exists\, x\!:\ ax\equiv n\pmod b,\:$ so $\rm\:n = ax + by,\:$ and $\rm\:0
$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\,$ ...
-
1I 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.) – 2012-10-18
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)$