$\gcd(a,b,c)=\gcd(\gcd(a,b),c)\,$ [Associative Law for GCD, LCM]

Solution 1:

Hint $ $ By $\,\color{#c00}{\rm U}= $ gcd Universal Property (see below) we have

$$d\mid(a,b,c)\!\!\color{#c00}{\overset{\rm\ U}\iff} d\mid a,b,c\!\!\color{#c00}{\overset{\rm\ U}\iff} d\,\mid (a,b),c\!\!\color{#c00}{\overset{\rm\ U}\iff} d\mid ((a,b),c)\qquad$$

So $\,(a,b,c)\,$ & $\,((a,b),c)\,$ divide each other (let $\,d\,$ equal each above) so they're equal, being $> 0$.

This is the associative property of the GCD. In the same way, by induction, we can erase (or normalize) brackets in $n$-argument gcds, showing general associativity of the gcd, e.g. see here.

Remark $\ $ For completeness, below is a proof of $\,\color{#c00}{\rm U}= $ gcd Universal Property.

Lemma $\ \ d\mid a_1,\ldots,a_n\!\overset{\rm\color{#c00}U\!\!}\iff d\mid (a_1,\ldots,a_n)\ \ \ $ [GCD Universal Property]

${\bf Proof}\quad\ d\mid a_1,\ldots,a_n\Rightarrow\, d\mid (a_1,\ldots,a_n) = j_1 a_1\!+\ldots+j_n a_n\,$ for some $\, j_i\in\Bbb Z,\,$ by Bezout.

$\qquad\qquad\, d\mid (a_1,\ldots,a_n)\mid a_1,\ldots,a_n\,\Rightarrow\, d\mid a_1,\ldots,a_n\,$ by transitivity of $ $ "divides",

The second divisibility in the prior line is due to the gcd being a common divisor of its arguments.

Remark $ $ Dually, as above, associativity of LCM is immediate from the universal property of LCM

Lemma $\ \ a_1,\ldots,a_n\mid m\iff {\rm lcm}(a_1,\ldots,a_n)\mid m\ \ \ $ [LCM Universal Property]

These universal properties are the definitions of GCD & LCM in more general rings - where the Bezout identity need not hold true, e.g. in $\,\Bbb Z[x]\,$ and $\,\Bbb Q[x,y]\,$ where the gcds $\,(x,2) = 1 = (x,y)\,$ cannot be written as linear combinations. Follow the links for further details.

Application to computation (Bezout) $ $ We can exploit gcd associativity to reduce many-argument (extended) gcd computations to compositions of two-argument (extended) gcds, e.g.

$$(a,b,c) = ((a,b),c) = i(a,b)+jc = i(ka\!+\!\ell b)+jc = ik\:\!a + i\ell\:\!b + j\:\!c\qquad$$

where $\,k,\ell\,$ are Bezout coefs for $\,e:=(a,b) = ka+\ell b,\,$ and $\,i,j\,$ for $(e,c) = ie+jc$

Algebraically the key idea is that integer linear combinations of $\,a,b,c\,$ are closed under integer linear combinations - which combined with gcd associativity allows us to decompose many-argument gcds in any way we please (as long as all arguments are included). This innate linearity is clarified when one studies ideals and modules.

Alternatively, we can directly apply the forward (extended) Euclidean algorithm, e.g, as here, which generally will be more efficient for many-argument gcds.

Solution 2:

The def of $d=\gcd(a,b)$ is $d|a$ and $d|b$ and if $f|a$ and $f|b$ then $f|d$.

Suppose $x=\gcd(a,b,c)$. Then $x|a$ and $x|b$ and $x|c$ so $x|\gcd(a,b)$ and $x|c$, so $x|\gcd(\gcd(a,b),c)$. Conversely if $x=\gcd(\gcd(a,b),c)$ then $x|\gcd(a,b)$ and $x|c$. So $x|a$ and $x|b$ and $x|c$, so $x|\gcd(a,b,c)$. Thus $\gcd(a,b,c) | \gcd(\gcd(a,b),c)$ and $\gcd(\gcd(a,b),c)| \gcd(a,b,c)$. Therefore $\gcd(\gcd(a,b),c) = \gcd(a,b,c)$