# 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 $$m,n$$ 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? Sep 23, 2011 at 14:44
• @OlivierBégassat: No, I'm searching for solutions in the natural numbers, not just the integers. Sep 23, 2011 at 14:49
• @HenningMakholm: Ah, right, my bad; I forgot to mention that. Fixed, thanks. Sep 23, 2011 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? Sep 23, 2011 at 15:10
• @DJC: Nah, the original question also said positive linear combination, but only in 1 place. No worries. :) Sep 23, 2011 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! Sep 23, 2011 at 15:59
• Remark: the unproven claim "the $m$ numbers..." is equivalent to $\,ny\equiv k\pmod{\!m}\,$ has a solution $\,y=b\,$ with $\,0\le b< m,\,$ which follows from well-known properties of congruences, e.g. take $\, b = n^{-1}k\bmod m,\,$ where $\,n^{-1}\bmod m\,$ exists by $\,\gcd(n,m)= 1\,$ (e.g. by the Bezout GCD identity). Jan 4, 2020 at 7:34
• I like this proof, however I have a doubt: in part (b), when you conclude by contradiction that if $a$ is negative, then $am+bn$ can be at most $mn-m-n$, it seems to me that you have assumed (not proved) that all non negative numbers smaller than $mn-m-n$ can't be represented with a non-negative linear combination of the integers $m,n$ , but your point (a) does not prove that right?it only proved that in particular $mn-m-n$ can't be represented with a non-negative linear combination of the integers $m,n$, but not for the one smaller than that, or am I missing something? May 28, 2021 at 22:09

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.

– Koro
Apr 10 at 10:15

We give two proofs below - first a purely arithmetical proof, then a more geometric version.

First we consider positive solutions $$\,x,y\ge 1,\,$$ then we generalize that to $$\,x,y\ge c\,\,$$ by a shift. Below we use these well-known results: $$\,\gcd(m,n)=1\,$$ $$\Rightarrow\,\color{#90f}{m^{-1}\ \rm exists}$$ $$\!\bmod {n}\,$$ (e.g. by the Bezout gcd identity) and furthermore $$\,m\mid nk\color{#4bf}{\overset{\!\rm \small E}\Rightarrow} m\mid k\:$$ (by $$\, \color{#4bf}{\rm \small E} =$$ Euclid's Lemma).

$$mx+ny = \color{#0a0}{k > mn}\,$$ is $$\rm\color{#0a0}{solvable}$$ for $$\,x,y\ge 1,\,$$ by mod $$n\!:\,$$ $$\rm\color{#90f}{there\ is}$$ an $$\,x\equiv \color{#90f}{m^{-1}}k\,$$ with $$\, 1\le \color{darkorange}{x \le n},\,$$ so $$\, mx \equiv k,\,$$ so $$\,m x + n y = k,\,$$ for $$\, y\in\Bbb Z,\,$$ and $$\,y>0\,$$ by $$\,m\color{darkorange}x \le \color{#0a0}m\color{darkorange}{n}\color{#0a0}{< k}$$

$$mx+ny\: \color{#c00}{{\bf =}\: mn}\,$$ is $$\rm\color{#c00}{unsolvable}$$ by $$\, m\:\!|\:\! ny\ \smash[t]{\color{#4bf}{\overset{\rm \small E}\Rightarrow}}\ m\:\!|\:\!y\$$ so $$\ x+n(y/m) = n\,$$ contra $$\,x,y/m \ge 1$$

Remark $$\$$ A simple shift translates the above to handle $$\,x,y \ge c,\,$$ viz. \,\ \ \ \ \ \ \begin{align} &\ \ \ \ \, m\,x^{\phantom{|^|}} \ \:\!+\ \ \ \ n\,y\ \ \ \ =\ k\qquad\qquad\quad\ \:\!{\rm for}\ \ x,y \ge c = \bar c\!+\!1\\[.2em] \iff\ &m(x\!-\!\bar c) + n(y\!-\!\bar c) =\, k\!-\!\bar c(m\!+\!n)\,\ \ {\rm for}\ \ x\!-\!\bar c,\,y\!-\!\bar c\:\!\ge\:\! 1,\ \text{so by above}\\[.2em] &{\rm this\ \ is\ \underset{\textstyle\color{#c00}{unsolvable}}{\color{#0a0}{solvable}}\ for}\ \ \,k\!-\!\bar c(m\!+\!n)\underset{\textstyle\color{#c00}{\bf =^{\phantom{-}\!\!\!\!}}}{\bf \color{#0a0}>} mn\ \ {\rm i.e.}\ \ k \underset{\textstyle\color{#c00}{\bf =^{\phantom{-}\!\!\!\!}}}{\bf \color{#0a0}>} mn\!+\!\bar c(m\!+\!n)\\[.1em] \end{align}

The bound $$\, {\cal F}_c = mn + (c\!-\!1)(m\!+\!n)\,$$ is known as the Frobenius number. The most common cases  are: $$\ {\cal F}_0 = mn-m-n;\:$$ $$\:{\cal F}_1 = mn.\,$$ Note $$\,{\cal F}_c\,$$ is sometimes called modified if $$\,c\neq 0.$$

Below is a more geometric proof that $$\,{\cal F}_0 = mn-m-n$$.

Key Idea  In the plane $$\,\mathbb R^2,\,$$ a line $$\rm\,a\,x+b\,y = c\,$$ of negative slope has points in the first quadrant $$\rm\,x,y\ge 0\$$ iff its $$\rm\,y$$-intercept $$\rm\,(0,\,y_0)\,$$ is in the first quadrant, i.e. $$\,\rm y_0 \ge 0\,.$$ We can use an analogous "normalized" point test to check if a discrete line $$\rm\,m\,x + n\,y = k\,$$ has points in the first quadrant.

By above (or linear diophantine theory) the general solution $$\rm\,(x,y)\,$$ of $$\,\rm mx+ny = k\,$$ is obtained by adding to a particular solution $$\,(x_0,y_0)\,$$ arbitrary integer multiples of $$\,\rm (-n,m).\,$$ Doing so we can normalize any solution to one in "least terms", i.e. having the least possible value of $$\rm\,x\in\Bbb N$$.

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

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

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

Since $$\rm\, k = m\ x + n\ y\,$$ is increasing in both $$\rm\,x\,$$ and $$\rm\,y,\,$$ the largest non-representable $$\rm\,k\,$$ has normalization $$\rm\,(x,y) = (n\!-\!1,-1),\,$$ i.e. the lattice point that is rightmost (max $$\rm\,x$$) and topmost (max $$\rm\,y$$) in the nonrepresentable lower half $$\rm (y < 0)$$ of the normalized strip, i.e. the vertical strip where $$\rm\, 0\le x \le n-1.\,$$ Thus $$\rm\,(x,y) = (\color{#0a0}{n\!-\!1},\color{#c00}{-1})\,$$ yields that $$\rm\, k = mx+ny =$$ $$\rm m\,(\color{#0a0}{n\!-\!1})+n\,(\color{#c00}{-1}) =$$ $$\rm mn\! -\! m\! -\! n\$$ is the largest nonrepresentable integer. $$\$$ QED

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

Remark $$\$$ 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)$? Sep 23, 2011 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". Sep 23, 2011 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)\:.$ Sep 23, 2011 at 18:46
• See here for an inductive proof. May 28, 2021 at 21:21

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. Apr 18, 2012 at 3:09