# Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$.

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\iff d\,\mid (a,b),c\!\!\!\color{#c00}{\overset{\rm\ U}\iff} d\mid ((a,b),c)$$

Remark $$\$$ For completeness, below is a proof of the two $$\rm\color{#c00}{red\ arrows\ U}$$

Lemma $$\ \ d\mid a,b,c\iff d\mid (a,b,c)\ \ \$$ [GCD Universal Property]

$${\bf Proof}\quad\ d\mid a,b,c\,\Rightarrow\, d\mid (a,b,c)\,$$ by $$\ (a,b,c) = ia\!+\!jb\!+\!kc,\ i,j,k\in\Bbb Z,\,$$ by Bezout.

$$\qquad\qquad\, d\mid (a,b,c)\Rightarrow d\mid a,b,c\$$ by $$\ (a,b,c)\mid a,b,c\,$$ and transitivity of  "divides".

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.

Dually we have the universal property of LCM

Lemma $$\ \ a,b,c\mid m\iff {\rm lcm}(a,b,c)\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

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