Prove that $\gcd(a,b,c) = \gcd(\gcd(a,b),\gcd(a,c))$

Question

I have tried to prove this statement the following way:

We will call $d_1=\gcd(a,b)$, $d_2=\gcd(a,c)$, $d=\gcd(d_1,d_2)$ and $D=\gcd(a,b,c)$.

We know that:

• $d_1 \mid a$ and $d_1 \mid a$
• $d_2 \mid a$ and $d_2 \mid c$
• $d \mid d_1$ and $d \mid d_2$

So, if $d \mid d_1$ and $d_1 \mid a$, we know that $d \mid a$.

The same can be said to conclude that $d \mid b$ and $d \mid c$.

We know that if $D=\gcd(a,b,c)$, this means that $D \mid a$, $D \mid b$ and $D \mid c$.

As we can see both $D$ and $d$ divide $a$, $b$ and $c$, so we can conclude that $\gcd(a,b,c) = \gcd(\gcd(a,b),\gcd(a,c))$.

Is this proof conclusion correct?

Answer 1

You have proved that $d$ and $D$ are common divisors - but are they the same?

$D$ is the greatest so $d\le D$,but you need to prove the reverse inequality to conclude your proof.

For example both $2$ and $6$ divide the numbers $6, 30, 72$ but $2\neq 6$ so you can't include that two common divisors are equal.

It should be easy enough to fill the gap - at the moment you haven't quite tied down the relationship between $d$ and $D$.

Answer 2

The proof is incomplete and you would have to show $d = D$.

Hint

How you can proceed is that as $(a,b,c) = D$, then $d|D$, then try to prove $D|d$.

Read Ahead if you are not able to prove from the hint

Proof Continuation-

As $D$ divides $a,b,c$, it should divide $d_1$ and $d_2$ as both are $d_1 = (a,b)$ and $d_2 = (a,c)$.

This means that $D|d$ which is the $gcd$ of $d_1$ and $d_2$.

But $d|D$, this means $d = D$.