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.

Question

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

Answer 1

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.

Answer 2

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.