Theorem: Given any subset $S \subseteq N$ of the natural numbers, let $gcd(S) = k$, then there exists a constant $M \in N$ such that every $n \in N$, $n > M$ and $k \mid n$, can be written as a linear combination (with natural coefficients) of the elements in the subset; i.e.,
$$n = \alpha_{1}a_{1} + \alpha_{2}a_{2} + ... + \alpha_{n}a_{i} + ...$$
with $\alpha_{1}, \alpha_{2}, ..., \alpha_{i}, ... \in N$ and $a_{1}, a_{2}, ..., a_{i}, ... \in S$. Note that $S$ need not be finite.
Proof: We begin by observing that every linear combination of $S$ will be divisible by $k$; what needs to be shown then is that there is a point after which every multiple of $k$ is generated. This is certainly the case for linear combinations of two natural numbers; we can show it by induction on the multiples of $k$:
(Inductive step) Let $n$ be the first multiple of $k$ greater than M, then there exits (by assumption) $\alpha, \beta \in N$ such that $n = \alpha a + \beta b$. The next multiple of $k$ will be $n + k = \alpha a + \beta b + k$. From here, there are two cases: $\alpha \geq \mu$ and $\alpha < \mu$.
If $\alpha \geq \mu$, we can proceed by increasing $\beta$ and decreasing $\alpha$: $$n + k = (\alpha - \mu) a + (\beta + \phi) b$$
where $\mu$ and $\phi$ come from the equation $\mu a + k = \phi b$, whose solution is guaranteed to exists since $\mu x + 1 = \phi y$ always has a natural solution when $x$ and $y$ are coprimes (which $\frac{a}{k}$ and $\frac{b}{k}$ are!).
If $\alpha < \mu$, we can restart $a$:
$$n + k = (\alpha + \gamma) a + (\beta - \delta) b$$
where $\gamma$ and $\delta$ come from the equation $\delta b + k = \gamma a$, whose solution exists for the same reason.
(Base step) The selection of the base case now arises naturally; for we only need to pick $n$ high enough so that we can restart $a$. This also implies a value for M.
We can extend this result to any finite set $F \subset N$ by exploiting the definition of $gcd$ over multiple arguments:
$$gcd(a_{1}, a_{2}, ..., a_{n}) = gcd(a_{1}, gcd(a_{2}, ..., a_{n}))$$
We proceed by induction on the size of $F$:
(Base step) Let $\mid F \mid = 2$, then the solution stems from the previous result.
(Inductive step) Let $\mid F \mid = m$ and $gcd(a_{1}, ..., a_{m-1}) = l$, then assume there exists $M'$ such that every $n' \in N, n > M$ and $l \mid n'$, can be written as a linear combination (with natural coefficients) of $a_{1}, ..., a_{m-1}$; i.e.,
$$n' = \alpha_{1} a_{1} + \alpha_{2} a_{2} + ... + \alpha_{m-1} a_{m-1}$$
with $\alpha_{1}, \alpha_{2}, ..., \alpha_{m-1} \in N$ and $a_{1}, a_{2}, ... , a_{m-1} \in F-\{a_{m}\}$. If this assumption holds, then it also holds that there exists a prime $p$ such that $gcd(p, a_{m}) = 1$, $pl > M'$, and which can be written as a linear combination of $F - \{a_{m}\}$; from it we can see that $gcd(pl, a_{m}) = k$. Thus, every $n \in N, n > M$, can be written as a liner combination of $pl$ and $a_{m}$.
The jump to the infinite case relies on the following lemma.
Lemma: If $S \subseteq N$ is an infinite subset of the natural numbers and $gcd(S) = k$, then it contains a finite subset $S' \subset S$ such that $gcd(S') = gcd(S)$.
Proof: Let $n \in S$, then $k \mid n$ and $n = kp_{1}^{a_{1}}p_{2}^{a_{2}}...k_{m}^{a_{m}}$. Now, for each $1 \leq i \leq m$, select any $r_{i} \in S$ such that $kp_{i} \nmid r_{i}$. It's evident that $gcd(n, r_{1}, ..., r_{m}) = k$. Hence, $S' = \{n, r_{1}, ..., r_{m}\}$.