15
$\begingroup$

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?

  • 0
    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?2011-09-23
  • 0
    @OlivierBégassat: No, I'm searching for solutions in the natural numbers, not just the integers.2011-09-23
  • 0
    @HenningMakholm: Ah, right, my bad; I forgot to mention that. Fixed, thanks.2011-09-23
  • 0
    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?2011-09-23
  • 0
    A hint for part a: $mn-m-n = (m-1)n-m$, so a non-negative solution to that would also produce a non-negative solution for $(m-1)n$. Subtract that solution from $0m+(m-1)n$ and use the Chinese Remainder Theorem.2011-09-23
  • 0
    @HenningMakholm: Not really. :( If I set $mx + ny = mn - m - n$ then I get $m(x + 1) + n(y + 1) = mn$, but I'm not sure how to prove that this has no nonnegative solution.2011-09-23
  • 0
    @HenningMakholm: We haven't learned the Chinese Remainder Theorem so I'd need to learn that first...2011-09-23
  • 0
    Perhaps the CRT is overkill here. You could also just subtract the two solutions and derive a contradiction directly, I think.2011-09-23
  • 0
    This is a duplicate of [When do the multiples of two primes span all large enough natural numbers?](http://math.stackexchange.com/questions/8186/when-do-the-multiples-of-two-primes-span-all-large-enough-natural-numbers)2011-09-23
  • 0
    @MikeSpivey: I don't see any proof in your duplicate...2011-09-23
  • 0
    @Mehrdad: My hint doesn't help if $m,n$ are nonnegative. However, your original post said they were just integers....2011-09-23
  • 0
    @Mehrdad: I think the proof is in Qioachu Yuan's answer.2011-09-23
  • 1
    @DJC: Nah, the original question also said `positive linear combination`, but only in 1 place. No worries. :)2011-09-23
  • 0
    @Mehrdad: Not to nitpick, but a _positive linear combination_ is a linear combination which is positive. The integers themselves need not be positive. I cede the point, however, so I deleted the original hint.2011-09-23

5 Answers 5

8

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, 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
    +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!2011-09-23
6

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-y_0$. So we want to find $t$ such that $$-\frac{y_0}{m}

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}

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.

4

Below we show it's a discrete analog of this: 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.$

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.$ Therefore $\,(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 we are done; otherwise, by the lemma, $\,k\,$ has no rep with both $\,x,y\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.

  • 0
    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)$?2011-09-23
  • 1
    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".2011-09-23
  • 0
    @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)\:.$2011-09-23
2

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

0

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

  • 0
    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.2012-04-18