# 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?

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)$.

Idea for existence

Consider the set $A \subseteq \mathbb{Z}$ and the subgroup generated by it $\langle A \rangle$ (it will be the smallest subgroup containing the set $A$). Since you are in $\mathbb{Z}$, every subgroup is of the form $d\mathbb{Z}$ for some $d \geq 0$ and $d \in \mathbb{Z}$. This $d$ will be the $\gcd(A)$.

• That's a good insight, but I still don't know, that there are said $a_1, \dots, a_k \in A$. – Stefan Perko Dec 24 '14 at 20:35
• The finite sums $\sum_i x_i a_i$ form a group, and any group containing $A$ contains it. – Robert Israel Dec 24 '14 at 20:57
• I think I get it now: Since $d\in d\mathbb{Z} = \langle A \rangle$, there is a sum $\sum x_i a_i = d$. – Stefan Perko Dec 25 '14 at 7:41

Computationally, working with an infinite set (or even a set that may or may not be infinite) can be difficult.
For example, let $A$ be the set of perfect numbers. Its gcd is either $1$ or $2$, but we don't know which (the existence of an odd perfect number is a famous open problem).

• True, but for some sets we do know, what to do. Consider $d\mathbb{Z}$. Maybe there are other sets like this? – Stefan Perko Dec 25 '14 at 7:43