1
$\begingroup$

Let $a$ and $b$ be two relatively prime positive integers. Prove that every sufficiently large positive integer $N$ can be written as a linear combination $ax+by$ of $a$ and $b$ where $x$ and $y$ are both nonnegative, i.e. there is an integer $N_0$ such that for all $N\geq N_0$ the equation $ax+by=N$ can be solved with both $x$ and $y$ nonnegative integers.

Proof: Let $a,b$ be positive integers. Assume that $a$ and $b$ are relatively prime. i.e. $\gcd(a,b)=1$. i.e. $ax+by=1$ for some $x,y\in \mathbb{Z}$. How can I restrict this result to $x,y$ are positive integers?

Let $N$ be an integer such that $N\geq N_0$. Then $$ N = N(ax+by) = a(Nx)+b(Ny) $$ So $n$ can be written as a linear combination of $a$ and $b$.

$\endgroup$
1
$\begingroup$

Hint: Consider $N_0 = ab-a-b+1.$ To prove this consider the numbers $0,b,2b,...,(a-1)b$ and use the fact that they are all distinct modulo $a$ and thus represent all possible remainders modulo $a.$

On the other hand, the Euclidean algorithm approach you want to salvage seems not likely to work.

$\endgroup$
0
$\begingroup$

This is a supplement for the kind hint given by @dezdichado.

We only need to show that for all integer $N\ge ab+1$, the equation $ax+by=N$ can be solved with both $x$ and $y$ positive integers. Note that the difference of the statement here with that in the question is that we need $x$ and $y$ to be positive.

As @dezdichado mentioned, the $a$ numbers $b,2b,...,ab$ are all distinct modulo $a$ since the difference of any pair of them cannot be divided by $a$, and thus they represent all possible remainders modulo $a$.

Now for any integer $N\ge ab+1$, the remainder of $N$ molulo $a$ must be the same as that of $by$ molulo $a$, with $1\le y\le a$ an integer. That is, $a\mid(N-by)$. Then there exists a nonnegative integer $x$ such that $N=ax+by$, and it is easy to verify that $x$ cannot be zero. We are done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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