Proof of the Frobenius coin problem for two coins

Proof

Let $a > 1$ and $b > 1$ be coprime integers. Put $N = ab - a - b$. Here "natural number" includes $0$.

Part 1: $N$ is not of the form $ax + by$.

1. Suppose $N = ax + by$ with natural numbers $x$ and $y$. Then $ab = a(x + 1) + b(y + 1)$.
2. So $b(y + 1) = a(b - x - 1)$, and $a$ divides $b(y + 1)$.
3. Since $a$ and $b$ are coprime, the generalized Euclid's lemma gives $a \mid y + 1$. As $y + 1 \ge 1$, this forces $y + 1 \ge a$.
4. In the same way, $a(x + 1) = b(a - y - 1)$, so $b \mid x + 1$ and $x + 1 \ge b$.
5. Then $ab = a(x + 1) + b(y + 1) \ge ab + ab = 2ab$. This is false, since $ab > 0$. So no such $x$ and $y$ exist.

Part 2: every integer $n > N$ is of the form $ax + by$.

6. By Bézout's identity, there are integers $u$ and $v$ with $au + bv = 1$. So $a u \equiv 1 \pmod b$.
7. Let $n > N$ be an integer. By the division algorithm, there is an $x$ with $0 \le x \le b - 1$ and $x \equiv nu \pmod b$.
8. Then $ax \equiv anu \equiv n \pmod b$, so $y = (n - ax)/b$ is an integer, and $n = ax + by$.
9. Since $x \le b - 1$, we get $n - ax \ge n - a(b - 1) > N - ab + a = -b$.
10. So $by = n - ax > -b$, and $y > -1$. As $y$ is an integer, $y \ge 0$.
11. So $x$ and $y$ are natural numbers with $n = ax + by$.