# How do I show that any natural number of this expression is a natural linear combination?

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?

• See the coin problem for $n=2$, with $g(a,b)=ab-a-b$. – Dietrich Burde Jan 13 '18 at 16:10
• Not sure if it helps but $ab-a-b+1=a(b-1)-(b-1)=(a-1)(b-1)$. – kingW3 Jan 13 '18 at 16:20
• Thanks all. @DietrichBurde I can see the similarity between the coin problem and this, but I can't find related ideas that can help solve the induction problem. – oldselflearner1959 Jan 22 '18 at 1:09
• Do you include $0$ among the natural numbers or not ? – Ewan Delanoy Jan 22 '18 at 10:38

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.