Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 4 more comments

3 Answers

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
@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
show 8 more comments

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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