Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
homework should be tagged as such –  hmmmm Oct 18 '12 at 19:02
    
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

3 Answers 3

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

share|improve this answer

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

share|improve this answer
2  
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
1  
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
1  
It is tagged as "homework". Any less "skimpy"(?) would practially give away the whole answer instead of trying to hint only. –  DonAntonio Oct 18 '12 at 22:06

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.