Given that $ab - a - b$ cannot be expressed as a natural linear combination of $a$ and $b$, show that any natural number greater than $ab - a -b$ can be expressed as a natural linear combination of $a$ and $b$. A natural linear combination here means some $ak + bl$ where $k, l \in \mathbb{N}$, suppose $(a,b) = 1$.
At first thought I think I need to use induction since there are many cases to prove. But if I start with the base case $ab - a - b + 1$, I'm unable to proceed further since this cannot be factorized.
We try proof by cases: Let $ak + bl = c$ for some $k, l \in \mathbb{N}$, and $c > ab- a - b$.
Case 1: $k$ and $l$ are $\geq$ 0, so our case is true immediately.
But I don't know how we can use the other cases since the constraint is that the coefficients must be a natural number?
Let us first prove the following lemma :
Lemma : If $\gcd(a,b)=1$, then any integer greater than $ab$ can be expressed as $aX+bY$ where $X,Y$ are positive integers.
Proof :
If $\gcd(a,b)=1$, then there exist integers $m,n$ such that $am+bn=1$. So, the line $aX+bY=N$, i.e. $Y=-\frac abX+\frac Nb$ where $N$ is a positive integer passes through a lattice point. Considering the slope $-\frac ab$, we see that the lattice points on the line are at equal intervals $(b,-a)$.
For $N=ab$, we have $Y=-\frac abX+a$ which passes through $(b,0)$ and $(0,a)$. Therefore, considering the intervals of the lattice points, the equation $aX+bY=ab$ does not have any positive solutions.
For $N\gt ab$, considering again the intervals of the lattice points, we see that there is at least one positive solution for $aX+bY=N$. $\quad\blacksquare$
Let $x=X-1,y=Y-1$.
From the lemma, any integer greater than $ab$ can be expressed as $aX+bY=a(x+1)+b(y+1)=ax+by+a+b$ where $x,y$ are non-negative integers.
It follows that any integer greater than $ab-a-b$ can be expressed as $ax+by$ where $x,y$ are non-negative integers.