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.

  • $\begingroup$ Does $0$ belong to $\Bbb{N}$ in your convention? $\endgroup$ – Crostul Nov 21 '15 at 9:15
  • $\begingroup$ no it does not... $\endgroup$ – Zimkovic Nov 21 '15 at 9:19
  • $\begingroup$ You can suppose without loss of generality that $n=2$. Then, for the general case simply shift everything by $a_3+ \dots + a_n$. $\endgroup$ – Crostul Nov 21 '15 at 9:45
  • $\begingroup$ @Crostul this leaves the question how to show it for $n=2$ $\endgroup$ – Zimkovic Nov 21 '15 at 10:57
  • $\begingroup$ @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$. $\endgroup$ – 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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