Q:

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.

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

A:

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. 

