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
    Presumably in the definition of $N_m = $ 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?2010-12-09
  • 0
    @Rotwang: Yes, I had already edited that part before your comment. Thanks though.2010-12-09
  • 0
    If I'm not misreading this, you're also allowing $\alpha$ and $\beta$ to be 0, but not both at the same time.2010-12-09
  • 0
    @Jason DeVito: That's a good point. Yes, I was tacitly assuming that. I shall clarify.2010-12-09
  • 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
    **NOTE** $\ $ The Frobenius problem was [discussed here](http://math.stackexchange.com/q/8186/242) a month ago.2010-12-09
  • 0
    @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.2010-12-09
  • 0
    @Timothy: But the solutions don't depend upon that. It's the same problem as here.2010-12-09
  • 0
    @Bill: I interpreted the question a bit differently, given an $m$ are there $a,b$ with $(a,b)=1$, for which $m$ is the frobenius number of $a,b$.2010-12-09
  • 0
    @Bill Dubuque: I agree now, I had misread the solution.2010-12-09
  • 0
    @Moron: Either way the same technique(s) work. We need to do a better job with duplicate questions. The new mods will have plenty of work!2010-12-09
  • 0
    @Bill: I don't see this as a dupe. In fact I would say none of the answers (here, or in the thread you linked) have answered this question (the revised version) completely as asked. Tim clearly says he is interested in the set of $\lt a,b,m\gt$. My answer says that there is triple for every odd $m$ and none for even $m$, but does not, for instance characterize all the possible triplets given an $m$, etc. I do agree about the dupe issue in general, though. Just not regarding this one.2010-12-09
  • 0
    @Moron: I interpreted Bill's contention this way. If $(a,b)=1$, then Sylvester's solution answers the Frobenius problem and we can get all required triples in this case. If $(a,b)>1$, then any number which is not a multiple of $(a,b)$ cannot be represented this way. So there are no such triples in this case.2010-12-09
  • 0
    @Tim: I understand. I was looking at it as "given m, find a,b", which IMO makes it not a dupe. But, I guess it is upto you :-)2010-12-09
  • 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