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