# Combinatorial argument for numbers

As part of a bigger proof I want to show the following proposition, but unfortunately I did not make any progress on it:

Let $X:=\{a_1,...,a_n\} \subset \mathbb{N}$ such that $\text{gcd}(a_1,...,a_n)=1,$ then $$\exists n_0 \in \mathbb{N}: \mathbb{N} \backslash\{1,...,n_0\} \subset \{k_1a_1+\cdots+k_na_n; a_i \in X, k_i \in \mathbb{N}\}.$$

Does anybody here have an idea how to show this. In particular, I don't know how to bring the $\gcd$ into the game?

If anything is unclear, please let me know.

• Does $0$ belong to $\Bbb{N}$ in your convention? – Crostul Nov 21 '15 at 9:15
• no it does not... – Zimkovic Nov 21 '15 at 9:19
• You can suppose without loss of generality that $n=2$. Then, for the general case simply shift everything by $a_3+ \dots + a_n$. – Crostul Nov 21 '15 at 9:45
• @Crostul this leaves the question how to show it for $n=2$ – Zimkovic Nov 21 '15 at 10:57
• @Crostul I disagree, because the assumption that the gcd of all $n$ of the $a_i$'s is $1$ doesn't imply that the gcd of two of them is $1$. – Andreas Blass Nov 21 '15 at 11:51

Lemma 1. Let $G$ be a subgroup of $\Bbb Z$ and $G\ne\{0\}$. Then $G=r\Bbb Z$ for some $r\in\Bbb N$.

Proof. Let $x\in G$ with $x\ne 0$. As also $-x\in G$, we conclude that $G\cap \Bbb N\ne\emptyset$. Thus let $r=\min(G\cap\Bbb N)$. By the subgroup property, $r\Bbb Z\subseteq G$. Let $g\in G$. Then for $k:=\lfloor gr\rfloor\in\Bbb Z$ we have $kr\le g<(k+1)r$. As $g-kr\in G$ and $g-kr<r$ we cannot have $g-kr\in \Bbb N_0$ by minimialty of $r$. Hence $g\le kr$ and ultimately $g=kr\in r\Bbb Z$. We conclude $G=r\Bbb Z$. $\square$

Lemma 2. Let $a,b\in \Bbb N$, $d=\gcd(a,b)$. Then $a\Bbb Z+b\Bbb Z=d\Bbb Z$.

Proof. $a\Bbb Z+b\Bbb Z$ is a soubgroup of $\Bbb Z$ and by lemma 1 is of the form $r\Bbb Z$ for some $r\in\Bbb N$. From $a,b\in r\Bbb Z$ we conclude $e\mid a$, $e\mid b$, hence $e\mid d$ and $d\in e\Bbb Z$. On the other hand, $a\Bbb Z\subseteq d\Bbb Z$, $b\Bbb Z\subseteq d\Bbb Z$, hence $d\Bbb Z\subseteq e\Bbb Za\Bbb Z+b\Bbb Z\subseteq d\Bbb Z$ and finally the claim. $\square$

Lemma 3. Let $a,b\in \Bbb N$. Assume $a\Bbb Z\setminus(-\infty,N_a]\subseteq A\subseteq a\Bbb Z$ and $b\Bbb Z\setminus(-\infty,N_b]\subseteq B\subseteq b\Bbb Z$. Then $d\Bbb Z\setminus(-\infty,N_d]\subseteq A+B\subseteq d\Bbb Z$ where $d=\gcd(a,b)$ and $N_d=N_a+N_b+ab$.

Proof. The inclusion $A+B\subseteq d\Bbb Z$ follows from lemma 2. Let $x\in d\Bbb Z$ with $x\notin A+B$. Because $d\Bbb Z=a\Bbb Z+b\Bbb Z$, there are ways to write $x=na+mb$ with $n,m\in\Bbb Z$, i.e., $$S:=\{\,\langle n,m\rangle\in\Bbb Z^2\mid na+mb=x\,\}\ne\emptyset.$$ On the other hand, $x\notin A+B$ implies that $na\le N_a\lor mb\le N_b$ for all $\langle n,m\rangle\in S$, i.e., $\max\{N_a-na,N_b-mb\}\in\Bbb N\cup\{0\}$ for all $\langle n,m\rangle\in S$. Pick $\langle n,m\rangle\in S$ that minimizes $\max\{N_a-na,N_b-mb\}$. Assume $na\le N_a$. Then for $n'=n+b, m'=m-a$, we have $\langle n',m'\rangle \in S$, hence $\max\{N_a-n'a,N_b-m'b\}\ge \max\{N_a-na,N_b-mb\}\ge0$. As clearly $N_a-n'a<N_a-na$, we conclude $N_b-m'b\ge 0$. Then $$x=n'a+m'b=na+ab+m'b\le N_a+ab+N_b.$$ By symmetry, we arrive at the same conlusion if we assume $mb\le N_b$ instead. As one of $na\le N_a$, $mb\le N_b$ must hold we conlcude $x\le N_a+ab+N_b$ as desired. $\square$

Theorem. Let $a_1,\ldots,a_n\in\Bbb N$ and $d=\gcd(a_1,\ldots,a_n)$. Then $d\Bbb Z\setminus(-\infty,N]\subseteq a_1\Bbb N+\ldots+a_n\Bbb N\subseteq d\Bbb Z$ for some $N$.

Proof. This follows by induction on $n$ from lemma 3, simply by noting that $\Bbb N=a\Bbb Z\setminus (-\infty,0]$ and $\gcd(a_1,\ldots,a_n)=\gcd(\gcd(a_1,\ldots,a_{n-1}),a_n)$. $\square$