# $\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$

• Presumably none of the $a_i$ is allowed to be $0$, else we have to modify the theorem a little. Commented Jun 22, 2016 at 0:13
• what is the problem of having $a_1$ as 0? Commented Jun 22, 2016 at 0:15
• At least you would need one of $a_1,a_2$ to be non-zero for $D_1$ to exist. Commented Jun 22, 2016 at 0:19
• Not much. Of course some of the $a_i$ must be non-zero. And if we are unlucky and $a_1=a_2=0$ our algorithm is in trouble. So the statement of the theorem has to be modified a little. Commented Jun 22, 2016 at 0:20
• Theorem 2-1 states, given any two integers a and b not both zero. If $a_1=a_2....=a_n$, I would just put $D_{n-1}$ is undefined right? Commented Jun 22, 2016 at 0:21

## 1 Answer

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.

• so $d| (a,b,c,d)$ based on your definition but how would this show (a,b,c,d)=(((a,b),c),d) Commented Jun 22, 2016 at 2:01
• @TheMathNoob $\$ If $\,m,n>0\,$ have the same set of divisors $\,d\,$ then $\,m = n\,$ since then $\,m\mid m\,\Rightarrow\,m\mid n,\$ and $\ n\mid n\,\Rightarrow\,n\mid m.\$ Commented Jun 22, 2016 at 2:34
• how do we know here that set of divisors is the same?. You started with a set of divisors d and at then at thend we showed that $d|(a,b,c,d)$ which implies that $(a,b,c,d)$ have those divisor , but do we know that we don't miss any? Commented Jun 22, 2016 at 4:05
• @TheMathNoob The equivalences in the answer show d divides the first iff d divides the second. Commented Jun 22, 2016 at 4:10
• ok so it goes in both directions. In conclusion the set of divisors is the same. Commented Jun 22, 2016 at 4:16