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.

  • $\begingroup$ 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? $\endgroup$ – Rotwang Dec 9 '10 at 19:31
  • $\begingroup$ @Rotwang: Yes, I had already edited that part before your comment. Thanks though. $\endgroup$ – Timothy Wagner Dec 9 '10 at 19:32
  • $\begingroup$ If I'm not misreading this, you're also allowing $\alpha$ and $\beta$ to be 0, but not both at the same time. $\endgroup$ – Jason DeVito Dec 9 '10 at 19:33
  • $\begingroup$ @Jason DeVito: That's a good point. Yes, I was tacitly assuming that. I shall clarify. $\endgroup$ – Timothy Wagner Dec 9 '10 at 19:35
  • $\begingroup$ Search the web for Frobenius Number. $\endgroup$ – Aryabhata Dec 9 '10 at 19:45

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

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

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.

  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ NOTE $\ $ The Frobenius problem was discussed here a month ago. $\endgroup$ – Bill Dubuque Dec 9 '10 at 20:06
  • $\begingroup$ @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. $\endgroup$ – Timothy Wagner Dec 9 '10 at 20:10
  • $\begingroup$ @Timothy: But the solutions don't depend upon that. It's the same problem as here. $\endgroup$ – Bill Dubuque Dec 9 '10 at 20:18
  • $\begingroup$ @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$. $\endgroup$ – Aryabhata Dec 9 '10 at 20:21
  • $\begingroup$ @Bill Dubuque: I agree now, I had misread the solution. $\endgroup$ – Timothy Wagner Dec 9 '10 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.