Linear combination of natural numbers with positive coefficients

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!

• @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

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.

• I'll just add that numerical semigroups are also mentioned in several other posts on MSE. – Martin Sleziak Mar 31 '14 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 '14 at 12:29

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.

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.