3
$\begingroup$

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!

2 Answers 2

2

Here is one proof:

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

  • 3
    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)$.2011-09-22
2

$\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*}$