# Largest integer that can't be represented as a non-negative linear combination of $m, n = mn - m - n$? Why?

This seemingly simple question has really stumped me:

How do I prove that the largest integer that can't be represented with a non-negative linear combination of the integers $m, n$ is $mn - m - n$, assuming they are coprime?

I got as far as this, but now I can't figure out where to go:

$mx + ny = k$, where $k = mn - m - n + c$, for some $c > 0$

$\Rightarrow m(x + 1) + n(y + 1) = mn + c$

If I could only prove this must have a non-negative solution for $x$ and $y$, I'd be done... but I'm kind of stuck.

Any ideas?

-
I don't understand the question. Are you searching within $m.\mathbb{Z}+n.\mathbb{Z}=gcd(m,n).\mathbb{Z}$? Do you assume both $m$ and $n$ to be positive? –  Olivier Bégassat Sep 23 '11 at 14:44
@OlivierBégassat: No, I'm searching for solutions in the natural numbers, not just the integers. –  Mehrdad Sep 23 '11 at 14:49
@HenningMakholm: Ah, right, my bad; I forgot to mention that. Fixed, thanks. –  Mehrdad Sep 23 '11 at 14:54
So you need to prove (a) $nm-m-n$ is not a non-negative linear combination ($mn$ itself fails to be a positive combination), and (b) that every $k \ge (n-1)(m-1)$ is a non-negative linear combination. Is there one of these halves you have already figured out? –  Henning Makholm Sep 23 '11 at 15:10
@DJC: Nah, the original question also said positive linear combination, but only in 1 place. No worries. :) –  Mehrdad Sep 23 '11 at 18:13

Here's an alternative (but perhaps more pedestrian) proof:

(a) $mn-m-n$ is not a non-negative linear combination: Assume, to the contrary, that $mn-m-n=am+bn$ with $a,b\in\mathbb N_0$. Then $$(a+1)m+bn=mn-n=(m-1)n$$ $$(a+1)m = (m-1-b)n$$ But $(a+1)m$ is clearly positive and since $(a+1)m < mn-n < mn$, it is a positive number less than $mn$ that is a multiple of both $m$ and $n$, contradicting the assumption that that $m$ and $n$ are coprime.

(b) Every integer $k>mn-m-n$ is a non-negative linear combination. The $m$ numbers $0$, $n$, $2n$, ..., $(m-1)n$ represent all the different residue classes modulo $m$, so one of them must be congruent to $k$ modulo $m$. So $k=am+bn$ where $0\le b<m$, and we need to check that $a$ is non-negative. However, if $a$ is negative, $am+bn$ can be at most $(m-1)n-m = mn-m-n$.

-
+1 Oooh I think I get it! I'll try to do it myself again and hopefully I won't run into trouble. :) Thanks a lot, I appreciate it! –  Mehrdad Sep 23 '11 at 15:59

Let $m$ and $n$ be positive and relatively prime. We show that $mn$ is the largest integer that cannot be represented as a positive linear combination of $m$ and $n$, that is, as $mx+ny$ where $x$ and $y$ are positive integers. We then deduce the corresponding result for non-negative linear combinations. There are simpler proofs, but the one below fits naturally towards the beginning of a course in elementary number theory.

The proof consists of two parts: (i) $mn$ cannot be represented as a positive linear combination of $m$ and $n$, and (ii) every integer greater than $mn$ can be expressed as a positive linear combination of $m$ and $n$.

Non-Representability of $mn$: Suppose to the contrary that $mn=mx+ny$ where $x$ and $y$ are positive. Then $mx=n(m-y)$. Note that $m$ divides $n(m-y)$ and $m-y$ is positive. Since $m$ and $n$ are relatively prime, it follows that $m$ divides $m-y$. This is impossible, since $m>m-y>0$.

Representability of all integers $>mn$: Let $w$ be an integer greater than $mn$. We show that $w$ is representable.

Since $m$ and $n$ are relatively prime, some integer linear combination of $m$ and $n$ is equal to $1$. By multiplying through by $w$, we can find integers $x_0$, $y_0$ such that $$mx_0+ny_0=w.$$

Now let $t$ be any integer. It is easy to verify that $$m(x_0-tn)+ n(y_0+tm)=w.$$ We will show that we can choose $t$ so that $x_0-tn$ and $y_0+tm$ are both positive. Then setting $x=x_0-tn$ and $y=y_0+tm$ will give us the desired representation.

We want to choose $t$ such that $tn<x_0$ and $tm>-y_0$. So we want to find $t$ such that $$-\frac{y_0}{m} <t < \frac{x_0}{n}.$$

To show that we can find such an integer $t$, we look at the difference $$\frac{x_0}{n}-\left(-\frac{y_0}{m}\right).$$ But $$\frac{x_0}{n}-\left(-\frac{y_0}{m}\right)=\frac{mx_0+ny_0}{mn}=\frac{w}{mn}>1.$$ Since the interval $$-\frac{y_0}{m} <t < \frac{x_0}{n}$$ has length greater than $1$, it contains at least one integer $t$. This completes the proof.

In the same way, we can show that if $w>kmn$, then the equation $mx+ny=w$ has at least $k$ positive solutions.

Representability using non-negative $x$ and $y$: It is easy to see that $w$ is representable using positive integers if and only if $w-m-n$ is representable using non-negative integers. It follows that $mn-m-n$ is the largest number which is not representable using non-negative integers.

-

Hint  Normalize $\,k = m\, x + n\, y\,$ so $\,0 \le x < n\,$ by adding a multiple of $\,(-n,m)\,$ to $\,(x,y).$

Lemma $\ \ k = m\ x + n\ y\,$ for some integers $\,x,\,y \ge 0\,$ $\iff$ its normalization has $\,y \ge 0.$

Proof $\ (\Rightarrow)\$ If $\ x,\, y \ge 0,\,$ normalization adds $\,(-n,m)\,$ zero or more times, preserving $\,y \ge 0.\,$
$(\Leftarrow)\ \,$ If the normalized rep has $\ y < 0,\,$ then $\,k\,$ has no representation with $\ x,\,y \ge 0,\,$ since to shift so that $\,y > 0\,$ we must add $\,(-n,m)\,$ at least once, which forces $\,x < 0.\ \$ QED

Finally, notice that since $\ k = m\, x + n\, y\$ is increasing in both $\,x\,$ and $\,y,\,$ it is clear that the largest non-representable $\,k\,$ has normalization $\,(x,y) = (n\!-\!1,-1),\,$ i.e. the lattice point that is rightmost (max $\,x$) and topmost (max $\,y$) in the nonrepresentable lower half $(y < 0)$ of the normalized strip, i.e. the vertical strip where $\, 0\le x \le n-1.$ Thus $\,(x,y) = (n\!-\!1,-1)\,$ yields $\, k = m\,(n\!-\!1)+n\,(-1) = m\,n - m - n\$ is the largest with no such representation. $\ \$ QED

Notice that the proof has a vivid geometric picture: representations of $\,k\,$ correspond to lattice points $\,(x,y)\,$ on the line $\, n\, y + m\, x = k\,$ with negative slope $\, = -m/n.\,$ Normalization is achieved by shifting forward/backward along the line by integral multiples of the vector $\,(-n,m)\,$ until one lands in the normal strip where $\,0 \le x \le n\!-\!1.\,$ If the normalized rep has $\,y\ge 0\,$ then that we are done; otherwise, by the lemma, $\,k\,$ has no rep with both $\,x,y\ge 0.\,$ This is a discrete analog of the fact that, in the plane $\,\mathbb R^2,\,$ a line of negative slope has points in the first quadrant $\,x,y\ge 0\$ iff its $\,y$-intercept $\,(0,\,y_0)\,$ lies in the first quadrant, i.e. $\, y_0 \ge 0.$

There is much literature on this classical problem. To locate such work you should ensure that you search on the many aliases, e.g. postage stamp problem, Sylvester/Frobenius problem, Diophantine problem of Frobenius, Frobenius conductor, money changing, coin changing, change making problems, h-basis and asymptotic bases in additive number theory, integer programming algorithms and Gomory cuts, knapsack problems and greedy algorithms, etc.

-
Sorry but the last 2 sentences of your proof aren't at all clear to me. Why does doing that shift x < 0, and why is the normalization "clearly" $(q - 1, -1)$? –  Mehrdad Sep 23 '11 at 15:32
Being normalized means $\rm\: 0 \le x < n\:$ so adding $\rm\:(-n,m)\:$ to $\rm\:(x,y)\:$ results in $\rm\:x < 0\:.\:$ The $\rm\:q\:$ was a typo for $\rm\:n\:.$ Make sure you grok the "vivid picture". –  Bill Dubuque Sep 23 '11 at 15:37
@Meh Note that the hypothesis $\rm\:\gcd(m,n) = 1\:$ is used implicitly in the proof of the Lemma, viz. the direction $(\Leftarrow)$ assumes that any two solutions differ by a multiple of $\rm\:(-n,m)\:.$ –  Bill Dubuque Sep 23 '11 at 18:46

Here's another version of the proof. Make a chart of the nonnegative integers in rows of size $m$, then mark the first $m$ multiples of $n$ (from 0 up to but not including $mn$). For example, if $m=4$ and $n=7$, we have the chart below with the first 4 multiples of 7 marked with a * :

\begin{array} & 0* & 1 & 2 & 3 \\ 4 & 5 & 6 & 7* \\ 8 & 9 & 10 & 11 \\ 12 & 13 & 14* & 15 \\ 16 & 17 & 18 & 19 \\ 20 & 21* & 22 & 23 \\ 24 & 25 & 26 & 27 \\ 28 & 29 & 30 & 31 \\ \ldots \end{array}

Now observe:

1. Every column has exactly one marked value. (This follows from (m,n)=1.)
2. The marked values, and all values below in the same column, are all representable as non-negative linear combinations of $m$ and $n$.
3. Conversely, any representable non-negative integer $mx+ny$ lies on or below the marked value in its column. (For $mx+ny$ must be $x$ rows below the value $ny$, which is a multiple of $n$ and therefore lies on or below a marked value.)

Therefore, the largest non-representable number lies one row above the largest marked number. This is $(m-1)n -m = mn - n -m$.

-

I think the easiest way to get the idea is as follows. Below are two basic facts that lead almost immediately to the answer. Assume that $m<n$ and $s=0\ldots(n-1)$.

1. If $nk+s$ is representable as a non-negative linear combination of $m$ and $n$, then $n(k+1)+s$, $n(k+2)+s$ etc. are representable as well.

2. If $nk+s$ is the least positive number of this form that is representable as a non-negative linear combination of $m$ and $n$, then $nk+s=mt$ for some positive $t$ (indeed, otherwise if $nk+s=mt+nu,u>0$, then we can subtract $n$, and $n(k-1)+s$ will still be representable).

Now, from these two facts: for each $s=0\ldots(n-1)$ we can find the least $t_s$ such that $mt_s\equiv s \mod n$, and if $t_{s'}$ is the largest among all $t_s$'s then $mt_{s'}-n$ is the largest number that cannot be represented as a non-negative linear combination. Since $m$ and $n$ are coprime, there is a one-to-one correspondence between $t_s\in\{1,\ldots,n-1\}$ and $s\in\{1,\ldots,n-1\}$, and $t_{s'}=n-1$ for $s'=n-m$. Hence, the largest non-representable number is $m(n-1)-n=mn-m-n$.

-
I think, a good thing about this approach is that you do need to remember the answer and prove it, i.e. prove that you cannot represent the number given but you can represent any larger number. Instead, it shows how to easily obtain the answer even if you do not know/remember it. –  Vadim Apr 18 '12 at 3:09