# Does $\gcd(I)=1$ imply the monoid generated by $I$ is $\mathbb{N}$ minus finitely many numbers?

This is true if $$I=\{a_1,\dots,a_n\}$$ is a finite set of positive integers. Namely, if $$\gcd(a_1,\dots,a_n)=1$$, then for all sufficiently large $$N$$ there is a non-negative integer solution $$(k_1,\dots,k_n)$$ to $$k_1a_1+\cdots+k_na_n = N.$$ In other words, the monoid generated by $$I$$ consists of every natural number except for possibly finitely many exceptions.

I want to consider an infinite set $$I=\{a_1,a_2,\dots\}$$ an infinite set of positive integers with $$\gcd(a_1,a_2,\dots)=1$$. Then is it true that for all sufficiently large $$N$$ there is a non-negative integer solution $$(k_1,k_2,\dots)$$ to $$k_1a_1+k_2a_2+\cdots = N$$ where $$k_i=0$$ for all but finitely many $$i$$?

My attempt: It's enough to find a finite subset of $$I$$ with gcd 1, and then we can apply the result of the finite case. To do this, set $$b_1=a_1$$. Then $$b_1$$ has finitely many prime factors, and we can let $$p$$ be the smallest. Since $$\gcd(a_1,a_2,\cdots)=1$$, there exists $$a_i$$ such that $$p \nmid a_i$$. Set $$b_2=a_i$$. Now $$\gcd(b_1,b_2)$$ has strictly fewer prime factors than $$b_1$$ (since $$p$$ is not one of them), and we can let $$p'$$ be the smallest. Again, there must be $$a_j$$ such that $$p' \nmid a_j$$, so set $$b_3=a_j$$. Then $$\gcd(b_1,b_2,b_3)$$ has strictly fewer prime factors than $$\gcd(b_1,b_2)$$. Continue in this fashion, and since the number of prime factors of $$\gcd(b_1,\dots,b_t)$$ is strictly decreasing with $$t$$, there must be $$T$$ such that $$\gcd(b_1,\dots,b_T)=1$$. Is this correct? Is there a simpler way to arrive at this result?

• Do we have $\gcd(a_1,a_2,\cdots)=1$ ? Commented Mar 19, 2020 at 21:22
• @Peter Yes, sorry I left out the "$=1$". Thanks for your comment! That does simplify the argument slightly.
– kccu
Commented Mar 19, 2020 at 21:30
• But I am not sure whether my argument was correct, so I deleted it. Commented Mar 19, 2020 at 21:31
• $(6,10,15)$ is a set with gcd 1, but 6 is not coprime to 10 or 15 Commented Mar 19, 2020 at 21:33
• But what is true, if we find a_j for every prime factor, then no prime can divide all entries, so the gcd must be 1 Commented Mar 19, 2020 at 21:34

Your idea is good. It can be formalized in a clearer way.

For a finite subset $$F$$ of $$I$$, define $$d(F)$$ to be the gcd of the members of $$F$$. It is easy to show that if $$F_1\subseteq F_2$$, then $$d(F_2)$$ is a divisor of $$d(F_1)$$.

Then there exists $$G$$ such that $$d(G)$$ is minimal. I contend that $$d(G)$$ is $$1$$. Indeed, if $$p$$ is a prime divisor of $$d(G)>1$$, we can find $$b\in I$$ such that $$p\nmid b$$, otherwise every element of $$I$$ would be divisible by $$p$$.

Then $$p\nmid d(G\cup\{b\})$$, so $$d(G\cup\{b\})$$ is a proper divisor of $$d(G)$$, hence smaller. Contradiction.

Finally, the submonoid generated by $$G$$ is contained in the submonoid generated by $$I$$. Since the former contains all positive integers from some point on, the same is true for the latter.

• Thank you, that argument is very clean!
– kccu
Commented Mar 20, 2020 at 1:21