# Showing the gcd of Integers can be Distributed

The Question: Use the theorem on classification of subgroups of $\mathbb{Z}$ to prove that, if $a_1,...,a_n \in \mathbb{Z}, gcd(a_1,...,a_n) = gcd(gcd(a_1,...,a_k),gcd(a_{k+1},...,a_n))$ for any $1 \le k \le n.$ The theorem, I believe, is that all integer subsets are multiples of the integers, then again aren't the modulo also subgroups? Also, I feel like I need to use Euclid's Algorithm, but I'm not sure where to start.

## 1 Answer

I'm guessing here as to how they intended you to solve this. Here is first some background on the structure of the subgroups of $\mathbb Z$ that I guess you should know.

Since $\mathbb Z$ is cyclic its subgroups are precisely the groups $n\cdot \mathbb Z$, for $n=0,1,2,3,\cdots$ (and no, the groups $\mathbb Z_n=\mathbb Z/n\cdot \mathbb Z$ are not subgroups of $\mathbb Z$, rather they are quotient groups of it). The in the lattice of subgroups of $\mathbb Z$, the intersection (i.e., meet) of $n_1\cdot \mathbb Z,\cdots n_k\cdot \mathbb Z$ is ${\rm lcm}(n_1,\cdots ,n_k)$ while the join (i.e., the smallest subgroup containing each $n_i\cdot \mathbb Z$) is ${\rm gcd}(n_1,\cdots,n_k)\cdot \mathbb Z$. So, you can now translate the claim bout the greatest common divisor to a property of joins in a lattice (namely, the a join of joins of things is the join of all the things - formalize this!). That lattice theoretic fact is quite easy to prove.

• I don't really understand this proof-but also we haven't learned much of this-and all of our work with gcd's was using the Euclidean Algorithm. Is there an alternative? – user82004 Sep 18 '13 at 8:21
• You can prove the result about the gcd directly, but since the question asked to do it via using the subgroup structure of the integers I thought of this proof. I'm not sure what they have in mind. – Ittay Weiss Sep 18 '13 at 9:22