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.

I'm searching for a reference for the following result, so as to avoid writing a full proof in a paper. Alternatively, if a one-liner exists, I'd be glad to know it!

Theorem: Let $a, b$ be two positive integers. Then there is a finite set $N$ of positive integers smaller than $\mbox{lcm}(a, b)$ such that: $$\{k_1a + k_2b \mid k_1, k_2 \in \mathbb{N}\} = \{\mbox{lcm}(a, b) + k\times\gcd(a, b) \mid k \in \mathbb{N}\} \cup N.$$

I'm also interested in its generalization to any number of integers: Say a set of integers is a linear set with $n$ periods if it can be written as: $$\{c_0 + \sum_{i=1}^n k_i \times c_i \mid k_i \in \mathbb{N}\}.$$ Then:

Theorem: Any linear set is the union of a finite set and a linear set with one period.

Thanks!

share|improve this question
    
@Byron: Thanks for the bounty. I'm indeed searching for a reference. –  Michaël Cadilhac Nov 11 '11 at 19:27
    
@Jyrki: Kiitos! Pointing out numerical semigroups helped me find Rosales and Garcia-Sanchez's book, and I thus phrased: "A linear set of dimension~1 can be expressed as the union of a finite set and a linear set with \emph{one} period: One possible way to see that is to consider $C = c_0 + P^*$ for some finite set $P$, and recall that $P^*$ is a numerical semigroup multiplied by a constant $k$ \cite[Proposition~2.2]{rosales-garcia09}, and thus is expressible as $k \times (\mathbb{N} \setminus F)$, with $F \subset \mathbb{N}$ a finite set." Would you please turn your comment into an answer? –  Michaël Cadilhac Nov 14 '11 at 20:37
    
I turned my comment into an answer as per your request. Deleting the now obsolete comment. –  Jyrki Lahtonen Nov 14 '11 at 21:15
add comment

3 Answers

up vote 2 down vote accepted
+250

The wikipedia article on numerical semigroups contains several references that may help you. I also recommend an answer by Robjohn to another question here in MSE. The question was about a particular case, but Robjohn covered the general case of a numerical semigroup generated by two coprime numbers very nicely.

share|improve this answer
    
I'll just add that numerical semigroups are also mentioned in several other posts on MSE. –  Martin Sleziak Mar 31 at 8:32
    
Thanks for the extra link, @Martin. It didn't feel right to receive a generous bounty for a Wikilink. It still doesn't. But it is the OP's call. –  Jyrki Lahtonen Mar 31 at 12:29
add comment

Some variant of the following result is proved in most books in elementary number theory.

Theorem: Let $a$ and $b$ be relatively prime positive integers. If $c >ab$, then there exist positive integers $x$ and $y$ such that $ax+by=c$.

The proof is not difficult. It is not quite a one-liner, largely because I am not a man of few words.

There are integers $x_0,y_0$, such that $ax_0+by_0=c$. Consequently, all integer solutions of the equation $ax+by=c$ have the shape $x=x_0+bt$, $y=y_0-at$, where $t$ ranges over the integers. To produce a positive solution, we want to find $t$ such that $x>0$ and $y>0$.

So we need $y_0-at >0$, $x_0+bt>0$, or equivalently $$-\frac{x_0}{b}<t <\frac{y_0}{a}.$$ The interval $(-x_0/b,y_0/a)$ has width $y_0/a+x_0/b$. which simplifies to $(ax_0+by_0)/ab$, that is, $c/ab$. If $c/ab>1$, then the interval is guaranteed to contain an integer $t$, and we are finished.

If $a$ and $b$ are not relatively prime, let $d=\gcd(a,b)$, and let $a=da'$, $b=db'$. Let $c$ be a multiple of $d$, say $c=c'd$. Then if $c'>a'b'$, $c$ is representable as a positive linear combination of $a$ and $b$. Equivalently, every multiple $c$ of $d$ which is greater than $ab/d$ is a positive linear combination of $a$ and $b$.

In particular, the $\text{lcm}(a,b)$ term in your expression puts us past the numbers that do not have a positive representation. The bound $ab/d$ is quite sharp.

The generalization to "many periods" is straightforward. Getting sharp bounds on the smallest number $m$ such that all $c$ that satisfy the necessary divisibility condition are representable may not be easy.

share|improve this answer
add comment

Let $c_1,\dots,c_n$ be positive integers and set $a=\gcd(c_1,\dots,c_n)$. By Bézout's identity, we can write $a=\sum_{i=1}^n z_i c_i$ for integers $z_i$.

Letting $c=\sum_{i=1}^n c_i$, every multiple $N$ of $a$ can be written as $N=qc+ra$ where $q,r$ are integers with $0\leq r<c/a$.

If $N$ is large enough, in particular if $N\geq c+\max_i |z_i|c^2/a$, then the coefficients in $N=\sum_{i=1}^n (q+z_ir) c_i$ are all non-negative. That is, every large multiple of $a$ can be written $N=\sum_{i=1}^n k_i c_i$ for non-negative integers $k_i$.

That is, $$\{c_0 + k a\mid k \in \mathbb{N}\}\setminus \{c_0 + \sum_{i=1}^n k_i c_i \mid k_i \in \mathbb{N}\}$$ is a finite set.

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