We give two proofs below - first a purely arithmetical proof, then a more geometric version.
First we handle the case of positive solutions $\,x,y\ge 1,\,$ then we perform a shift to handle $\,x,y\ge c.\,$ Below we use that $\,\gcd(m,n)=1\,\Rightarrow\, m^{-1}$ exists $\!\bmod {n}\,$ (e.g. by the Bezout gcd identity) and, furthermore, that $\,m\mid nk\,\Rightarrow\, m\mid k\,$ (e.g. by Euclid's Lemma).
$ mx+ny = \color{#0a0}{k > mn}\,$ is solvable for $\,x,y\ge 1,\,$ by mod $n\!:\, $ there is an $\,x\equiv m^{-1}k\,$ with $\, 1\le \color{#c00}{x \le n},\,$ so $\, mx \equiv k,\,$ so $\,m x + n y = k,\,$ for $\, y\in\Bbb Z,\,$ and $\,y>0\,$ by $\,m\color{#c00}x \le m\color{#c00}{n}\color{#0a0}{< k}$
$ mx+ny \color{#c00}{\bf =} mn\,$ is $\rm\color{#c00}{unsolvable}$ by $\, m\mid ny\,\Rightarrow\, m\mid 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,\,$ namely with $\,\bar c = c\!-\!1,$
$\,\ \ \ \ \ \begin{align} &\ \ \ \ \, m\,x^{\phantom{|^|}} \ \:\!+\ \ \ \ n\,y\ \ \ \ =\ \ \ \ k\qquad\quad\ \ \ \ \ \ \:\!{\rm for}\ \ x,y \ge c = \bar c\!+\!1\\[.1em]
\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}\\[.1em]
&{\rm this\ \ is\ \underset{\textstyle\color{#c00}{unsolvable}}{ solvable}\ for}\ \ \,k\!-\!\bar c(m\!+\!n)\underset{\textstyle\color{#c00}{\bf =^{\phantom{-}\!\!\!\!}}}> mn\ \ {\rm i.e.}\ \ k \underset{\textstyle\color{#c00}{\bf =^{\phantom{-}\!\!\!\!}}}> 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.\,$ It is sometimes called modified when $\,c\neq 0.$
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.
positive linear combination
, but only in 1 place. No worries. :) $\endgroup$ – user541686 Sep 23 '11 at 18:13