elementary number theory - Finding a linear combination of integers of infinite set $A$, that gives the gcd of $A$

This is a follow up to my previous question, were I asked for a proof, that for any nonnempty set of integers $A$, not all zero, the greastet common divisor of $A$ exists.

If $A$ is finite, with $A=\{a_1,\dots, a_k$} and $k = \#A$, then we can easily show, that there are $x_1, \dots, x_k\in \mathbb{Z}$ with $\gcd(A) = \sum_{i=1}^k x_ia_i$, and we can construct these integers. We use the extended euclidian algorithm and, if $k\geq 2$, the fact, that $\gcd(a_1, \dots, a_k) = \gcd(a_1, \gcd(a_2, \dots, a_k)$.

Now suppose $A$ is infinite:

1. How can we show, that there is a $k\in \mathbb{N}$, $a_1,\dots, a_k \in A$ and $x_1,\dots, x_k\in \mathbb{Z}$, with $\gcd(A) = \sum_{i=1}^k x_ia_i$?
   Alternatively:
   
   How can we prove the existence of some finite set $A'$, with $A'\subseteq A$ and $\gcd(A')=\gcd(A)$?


2. In what cases (for what sets) can we actually compute integers $k$ and $a_1, \dots, a_k$ with said property? (I'm looking for relatively general examples; not the exact class of sets, that satisfy this property)


3. When and how can we determine the least possible $k$? When and how can we determine the set of sets $A'$ with $A'\subseteq A$ and $\gcd(A')=\gcd(A)$, such that $\#A'$ is minimal?

Answer

Assume that $\gcd(A)=1$ (if not, just divide by the common factor). Let $a_0\in A$. If $a_0=1$, then we're done. Else, say $a_0=p_1^{e_1}\cdots p_n^{e_n}$. Since $A$ has gcd $1$, there exist $a_i\in A$ such that $p_i\nmid a_i$. Then $\gcd(a_0, a_1,\ldots, a_n)=1$.

To optimize this, select $a_0$ to have the least number of prime factors, choose $a_i$ to minimize the number of prime factors of $\gcd (a_0, a_1, \ldots, a_i)$.