Prove for relatively prime numbers.

Question

Prove that for relatively prime positive integers $a$ and $b$, the equation $ax+by=c$ must have non-negative integer solution if $c>ab-a-b$.

Answer 1

Outline: The equation has a solution $(x_0,y_0)$ in integers, one of which may be negative.

All solutions have shape $x=x_0-bt$, $y=y_0+at$, where $t$ ranges over the integers.

Choose $t$ so that $x_0-bt$ is non-negative, and as small as possible. Then $0\le x_0-bt\lt b$. Thus $x_0-bt\le b-1$, and $$b(y_0+at)=c-a(x_0-bt)\gt ab-a-b-a(b-1)=-b.$$ Since $b(y_0+at)\gt -b$, we must have $y_0+at\ge 0$. So we have found $t$ such that both $x_0-bt$ and $y_0+at$ are non-negative.