3
$\begingroup$

Let $m$ be a positive integer. Define $N_m:=\{x\in \mathbb{Z}: x>m\}$. I was wondering when does $N_m$ have a "basis" of two elements. I shall clarify what I mean by a basis of two elements: We shall say the positive integers $a,b$ generate $N_m$ and denote $N_m=$ if every element $x\in N_m$ can be written as $x=\alpha a+\beta b$ where $\alpha,\beta$ are nonnegative integers (not both zero) and no nonnegative linear combination (with at least one coefficient nonzero) of $a,b$ gives an element not in $N_m$.

More specifically, I want to understand the set $\{(a,b,m):N_m=\}$.

An example would be the triple $(2,3,1)$. Every positive integer greater than 1 can be written as $2\alpha +3\beta$ for nonnegative integers $\alpha,\beta$, for if it is even we can write it as $2\alpha$ for some positive integer $\alpha$ and if it is odd and greater than $3$ then we can write it as $3+2\alpha$ for some positive integer $\alpha$ and of course $3=1\cdot 3$. FInally the smallest integer a positive linear combination of $2,3$ can generate is $2$.

PS: Not quite sure what to tag this. Feel free to retag.

EDIT: After Jason's answer, it seems the first version of this question is more interesting, where the last condition in paragraph 1 is relaxed.

  • 0
    Search the web for Frobenius Number.2010-12-09

3 Answers 3

4

If $m$ and $n$ are coprime positive integers, then every integer with $>mn-m-n$ is expressible in the form $am+bn$ where $a$ and $b$ are nonnegative integers, but $mn-m-n$ isn't. This is due to Sylvester.

Added The key to the proof is the lemma that if $0\le k<(m-1)(n-1)$ then $k$ is representable iff $mn-n-m-k$ isn't. ISTR this involves a cunning use of the Chinese remainder theorem.

  • 0
    This is beautiful, thanks. Do you have a good reference for the proof? I was unable to find the wiki reference with a quick search.2010-12-09
4

This can only happen for the triple you found.

For, if $m=1$, then we must be able to generate 2, so we must take 2 in the basis. Likewise, we must be able to generate 3, so we must allow 3 in the basis.

If $m>1$, then we see by the same reasoning that $N_m$ must be generated by $m+1$ and $m+2$.

But then we can't express $m+3$: since $m>1$, we see if $\alpha >1$, then that $\alpha(m+1)\geq 2m + 2 > m+3$ . So, we must take $\alpha = 0$ or $1$. Then same reasoning applies to $\beta$.

If we take either of $\alpha$ and $\beta$ equal to $0$, then we just generate $m+1$ or $m+2$. Hence, we must take them both one.

Then $m+1 + m+2 = 2m+3 > m+3$.

  • 0
    Thanks. So it seems (with reference to Robin's answer and Moron's comment) its much more interesting, if we allow $a,b$ to generate a larger set and then define $N_m$ for the smallest possible $m$.2010-12-09
2

(Now that you have relaxed the last condition of paragraph 1)

I suppose you mean non negative $\alpha$, $\beta$? (You seem to be allowing them to be zero).

In which case, this looks like the Frobenius Problem which says that for $a,b$ such that $(a,b)=1$, every number greater than $(a-1)(b-1) - 1 $ is representable in the for $a\alpha + b \beta$ for $\alpha \ge 0, \beta \ge 0$.

Thus given an $m$, if a factorization of $m+1$ as $(a-1)(b-1)$ with $(a,b) = 1$ exists, then $N_m \subset \lt a, b \gt$.

If you are also looking for $m$ such that $m \notin \lt a, b \gt$ (the least such $m$) then there are $m$ for which there are no such $a,b$, as $m$ must necessarily be of the form $(a-1)(b-1) - 1$ with $(a,b) = 1$.

In fact we can characterize all such $m$.

If $m$ is even, there is no such representation (as both $a-1$ and $b-1$ must be odd).

If $m$ is odd, then $m+1 = (2-1)(m+2 - 1)$ and thus $a = 2, b = m+2$ will work.

  • 0
    @Moron: Yes, I read your earlier reply. I think I will just let it stay and will be happy to cast the 5th close vote, if others decide that's the way to go. FWIW, I found this answer to be most useful to me personally.2010-12-09