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

Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ for $0\ne a,b,c\in \Bbb{Z}$. I tried solving it with sets but I sense there are some details I am missing. I would truly appreciate your reference.

Hint $$\qquad 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)$$

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 the $$\rm\color{#c00}{red\ arrows\ U}$$

Lemma $$\ \ d\mid a_1,\ldots,a_n\!\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".

Dually we have 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.

• How is it concluded (generally) that for evry $d|a,b \Rightarrow$ $d|\gcd(a,b)$? – Meitar Abarbanel Mar 14 '15 at 13:51
• @Meitar See the added Remark. – Bill Dubuque Mar 14 '15 at 13:55
• Oh... I wasn't taught Bezout theorem. I shall look for it. – Meitar Abarbanel Mar 14 '15 at 13:59
• @Meitar I added a link to a simple, conceptual proof. – Bill Dubuque Mar 14 '15 at 14:01
• @Elvin $\ a\mid b\$ means $a$ divides $b,\,$ i.e. $\,an = b\,$ for some integer $\,n.\,$ This is widely used notation in number theory. – Bill Dubuque Sep 24 '19 at 13:48

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

• In the definition I was given, nothing is said about every divisor dividing the gcd. How is it shown? – Meitar Abarbanel Mar 14 '15 at 13:55
• It doesn't need to be shown, it's part of the definition, so you can assume it once you know $d=\gcd(a,b)$ then automatically any other divisor of $a$ and $b$ must divide $d$. – Gregory Grant Mar 14 '15 at 15:30
• Please post the definition you were given, so we can see how it differs from this one I gave. – Gregory Grant Mar 14 '15 at 15:30
• "The greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder." – Meitar Abarbanel Mar 14 '15 at 16:04

A different definition of gcd affords another proof.

For $$p_i\in \mathbb P \land p_i\mid abc$$, then $$a=\prod p_i^{\alpha_i},\ b=\prod p_i^{\beta_i},\ c=\prod p_i^{\gamma_i} \Rightarrow \gcd(a,b,c)=\prod p_i^{\min(\alpha_i,\beta_i,\gamma_i)}$$

Note that in some cases, an exponent $$\alpha_i,\beta_i,\gamma_i$$ will be $$0$$ when a particular $$p_i$$ is not a factor of one or another of $$a,b,c$$, but since $$p_i\mid abc$$, at least one of $$\alpha_i,\beta_i,\gamma_i$$ will be greater than $$0$$

Similarly, $$\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}$$

Hence, $$\gcd(\gcd(a,b),c)=\prod p_i^{\min({\min(\alpha_i,\beta_i)},\gamma_i)}=\prod p_i^{\min(\alpha_i,\beta_i,\gamma_i)}=\gcd(a,b,c)$$ QED

Since the minimum over a set is no greater than the minimum over a subset, \begin{align} \gcd(\gcd(a,b),c) &={\min_{u,v}}^+\!\left({\min_{x,y}}^+(ax+by)u+cv\right)\\ &\ge{\min_{x,y,z}}^+(ax+by+cz)\\ &=\gcd(a,b,c)\tag1 \end{align} $$\gcd(a,b)\mid a,b$$ and so $$\gcd(\gcd(a,b),c)\mid a,b,c$$. Thus, by the maximality of the gcd, $$\gcd(\gcd(a,b),c)\le\gcd(a,b,c)\tag2$$ $$(1)$$ and $$(2)$$ imply that $$\gcd(\gcd(a,b),c)=\gcd(a,b,c)\tag3$$

Proof: Let $$d=gcd(a,b,c)$$ for positive integers $$a$$,$$b$$, and $$c$$. Then $$d\mid a$$, $$d\mid b$$, and $$d\mid c$$. Hence, $$d\mid gcd(a,b)$$ and $$d\mid c$$ and so $$d\mid gcd(gcd(a,b),c)$$. Thus, $$d\mid f$$ where $$f=gcd(e,c)$$ and $$e=gcd(a,b)$$. Since $$f=gcd(e,c)$$, then $$f\mid e$$ and $$f\mid c$$. Hence, $$f\mid a$$, $$f\mid b$$, and $$f\mid c$$, so $$f\mid gcd(a,b,c)$$ which means $$f\mid d$$. Since $$d\mid f$$ and $$f\mid d$$, $$d=f$$.