# Subsets of natural numbers generated by two generators

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=<a,b>$ 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=<a,b>\}$.

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.

-
Presumably in the definition of $N_m = <a,b>$ you mean to include the condition that every number of the form $\alpha a + \beta b$, with $\alpha, \beta$ positive integers, should be in $N_m$, right? –  Rotwang Dec 9 '10 at 19:31
@Rotwang: Yes, I had already edited that part before your comment. Thanks though. –  Timothy Wagner Dec 9 '10 at 19:32
If I'm not misreading this, you're also allowing $\alpha$ and $\beta$ to be 0, but not both at the same time. –  Jason DeVito Dec 9 '10 at 19:33
@Jason DeVito: That's a good point. Yes, I was tacitly assuming that. I shall clarify. –  Timothy Wagner Dec 9 '10 at 19:35
Search the web for Frobenius Number. –  Aryabhata Dec 9 '10 at 19:45

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.

-
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. –  Timothy Wagner Dec 9 '10 at 19:42

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

-
@Moron: Thanks, again :) –  Timothy Wagner Dec 9 '10 at 20:05
NOTE $\$ The Frobenius problem was discussed here a month ago. –  Bill Dubuque Dec 9 '10 at 20:06
@Tim: No worries :-) –  Aryabhata Dec 9 '10 at 20:06
@Bill Dubuque: Thanks for the reference. There the OP is requiring the generators to be prime, which probably allows for an easier resolution of the Frobenius problem I think. –  Timothy Wagner Dec 9 '10 at 20:10
@Timothy: But the solutions don't depend upon that. It's the same problem as here. –  Bill Dubuque Dec 9 '10 at 20:18

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

-
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$. –  Timothy Wagner Dec 9 '10 at 19:48