# $\gcd$ proof relating to $\gcd$'s associativity and commutativity (I think)

I am trying to prove that the $\gcd(a,b,c)$ = $\gcd(\gcd(a,b),c)$.

I think it has something to do with $\gcd$'s being able to be represented by a linear combination (that is $\gcd(a,b) = ax + by > 0$, for some integer $x$ and $y$).

Any help is appreciated!

-

\begin{align*} d|\gcd(a,b,c) & \Longleftrightarrow d|a,b,c\\ &\Longleftrightarrow d|a,b\text{ and }d|c\\ &\Longleftrightarrow d|\gcd(a,b),c\\ &\Longleftrightarrow d|\gcd(\gcd(a,b),c). \end{align*}
If $d$ divides each of $a,b,c$ then $d|\gcd(a,b)$ and $d|c$. Conversely if $d|\gcd(a,b)$ and $d|c$ then $d$ divides each of $a,b,c$. Hence any number which divides $a$, $b$ and $c$ must also divide both $\gcd(a,b)$, $c$, and the converse is also true.
Since their divisors are identical, the greatest common divisor will also be the same, and we have $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$.
That's essentially the fact that set intersection is associative: $D(a,b,c)=D(a) \cap D(b) \cap D(c) = (D(a) \cap D(b)) \cap D(c)$ = $D(a,b) \cap D(c) = D(\gcd(a,b))\cap D(c) = D(\gcd(a,b),c)$. – lhf Sep 22 '11 at 11:18