4
$\begingroup$

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?
$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ That's a good insight, but I still don't know, that there are said $a_1, \dots, a_k \in A$. $\endgroup$ – Stefan Perko Dec 24 '14 at 20:35
  • $\begingroup$ The finite sums $\sum_i x_i a_i$ form a group, and any group containing $A$ contains it. $\endgroup$ – Robert Israel Dec 24 '14 at 20:57
  • $\begingroup$ 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$. $\endgroup$ – Stefan Perko Dec 25 '14 at 7:41
2
$\begingroup$

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

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

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.