1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ See the coin problem for $n=2$, with $g(a,b)=ab-a-b$. $\endgroup$ – Dietrich Burde Jan 13 '18 at 16:10
  • $\begingroup$ Not sure if it helps but $ab-a-b+1=a(b-1)-(b-1)=(a-1)(b-1)$. $\endgroup$ – kingW3 Jan 13 '18 at 16:20
  • $\begingroup$ 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. $\endgroup$ – oldselflearner1959 Jan 22 '18 at 1:09
  • $\begingroup$ Do you include $0$ among the natural numbers or not ? $\endgroup$ – Ewan Delanoy Jan 22 '18 at 10:38
2
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.