$\gcd(a_1,a_2,\ldots,a_n) = \gcd(\gcd(\gcd(a_1,a_2),a_3),\ldots.a_n)$ [gcd is associative]

Prove The GCD of more than two numbers, defined as that positive common divisor which is divisible by every common divisor, exists and can be found in the following way. Let there n numbers $a_1,a_2,...,a_n$ and define

$D_1=(a_1,a_2),D_2=(D_1,a_3),....,D_{n-1}=(D_{n-2},a_n)$

Then $(a_1,....,a_n)=D_{n-1}$

(a,b) refers to the gcd of a and b

Approach

Proof

Theorem 2-1 states, given any two integers a and b not both zero, there is a unique integer such that

i) $d>0$
ii) $d|a$ and $d|b$
iii) if $d_1$ is any integer such that $d_1|a$ and $d_1|b$, then $d_1|d$

Because we computed $D_{N-2}$, $D_{n-2}$ is divisible by every other divisor of $a_1,a_2,....,a_{n-1}$ by theorem 2-1, so the problem is reduced to considering all the divisors of $D_{n-2}$ and pick the greatest one that also divides $a_n$. This is equivalent to finding $D_{n-1}$, so $D_{n-1}$ by definition is divides $a_1,a_2,a_3....,a_n$

Solution 1:

Hint $ $ The general definition is equivalent to the $n$-ary form of the gcd Universal Property

$$d\mid (a_1,a_2,\ldots,a_n)\iff d\mid a_1,a_2,\ldots,a_n$$

The Theorem proves the case $\,n=2\,$ (better, see here). We can repeatedly apply this binary case to erase all the brackets in the left-associated $D_i$ as follows:

$$\begin{eqnarray} && d\mid (((a,b),c),d)\\ &\iff& d\mid ((a,b),c),d\\ &\iff& d\mid (a,b),c ,d\\ &\iff& d\mid a,b,c ,d\\ &\iff& d\mid (a,b,c ,d)\\ \end{eqnarray}$$

In the same way can erase the brackets from any such association, thus showing the general associativity of the gcd.