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?
 A: 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.
A: 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:


*

*Every column has exactly one marked value.  (This follows from (m,n)=1.)

*The marked values, and all values below in the same column, are all representable as non-negative linear combinations of $m$ and $n$.

*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 $.
A: 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$.
A: 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.
A: 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&ltn$ and $s=0\ldots(n-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.

*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$.
