1
$\begingroup$

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

  • 0
    I 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 3

2

Hint $\rm\:(a,b)=1\,\Rightarrow\, \exists\, x\!:\ ax\equiv n\pmod b,\:$ so $\rm\:n = ax + by,\:$ and $\rm\:0 0,\:$ by $\rm\:n > ab.$

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

  • 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.)2012-10-18
0

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