# How to prove $\gcd(a,\gcd(b, c)) = \gcd(\gcd(a, b), c)$?

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

The definition of GCD available to me is as follows:

Given integers a and b, there is one and only one number d with the following properties.

1. $d \geqslant 0$
2. $d|a$ and $d|b$
3. $e|a$ and $e|b$ implies $e|d$.

In the book that I am studying, prime factorization of numbers hasn't been taught yet. Only, the definition of GCD, I've given above has been taught and proven. So, I want to use only this to prove that $\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)$. Could you please help me?

-
Show that both sides equal gcd(a,b,c). –  franz lemmermeyer Feb 4 '12 at 19:21
I haven't encountered the definition of gcd of three numbers in the text yet and I am trying to avoid it. –  Lone Learner Feb 4 '12 at 19:26
Proof that GCD is associative –  pedja Feb 4 '12 at 20:01
@LoneLearner : The gcd of any number of numbers is the greatest of all of their common divisors, so you just need to know what a common divisor of three numbers is. The divisors of $12$ are $1,2,3,4,6,12$; the divisors of $15$ are $1,3,5,12$; the common divisors are just the members of the intersection of those sets of divisors (in this case $1,3$). So the question is: what's the definition of the intersection of three sets? The answer is that a thing is a member of the intersection precisely if it's a member of all three sets. –  Michael Hardy Feb 4 '12 at 21:08
By considering prime factorizations, it's a consequence of $\min(x,\min(y,z)) = \min(\min(x,y),z)$. –  lhf Feb 5 '12 at 1:34

Same answer as I just gave in sci.math...

Note that $$d|x,y\Longleftrightarrow d|\gcd(x,y).$$ So: \begin{align*} d|a,\gcd(b,c) &\Longleftrightarrow d|a,b,c\\ &\Longleftrightarrow d|\gcd(a,b),c \end{align*}

-
nice hint! (+1) –  robjohn Feb 4 '12 at 20:20
+1 for giving the cleanest proof possible (as far as I can see). My only gripe is with the notation: I would write $\;d|x \land d|y\;$ instead of $\;d|x,y\;$. Then the associativity of $\;\gcd\;$ translates directly to the associativity of $\;\land\;$. –  Marnix Klooster Jul 26 '13 at 9:41

Please note that this solution uses an idea that is very similar to the idea in the solution posted much earlier by ncmathsadist. The main difference is that it may contain fewer typos.

We show that for any integer $u$, if $u$ divides the left-hand side, then $u$ divides the right-hand side, and vice-versa. Thus the left-hand side and the right-hand side have the same set of common divisors, so must be equal, since they are both non-negative.

Now suppose that $u$ divides $\gcd(a, \gcd(b, c))$. Then $u$ divides $a$ and $u$ divides $\gcd(b,c)$. So $u$ divides $b$ and $c$, and therefore $a$, $b$, and $c$.

Now look at the right-hand side. We know that $u$ divides all of $a$, $b$, and $c$. So $u$ divides $\gcd(a,b)$, and therefore $u$ divides $\gcd(\gcd(a,b),c)$.

Showing that if $u$ divides the right-hand side, then $u$ divides the left-hand side is essentially the same calculation, and can be omitted.

-
I am trying a proof that strictly leads to the fact that if $d = gcd(a, gcd(b, c))$ then $d$ must satisfy the conditions $d|a$, $d|gcd(b, c)$, $e|a$ and $e|gcd(b, c)$ implies $e|gcd(a, gcd(b, c))$. Could you please tell me how to prove the last implication part? –  Lone Learner Feb 4 '12 at 21:03
@Lone Learner: It is inconvenient to work with $d$ directly, it is clearer to work with any common divisor. –  André Nicolas Feb 4 '12 at 21:07

First note that $(a,b) \mapsto \gcd(a,b)$ is symmetric in $a$ an $b$. Suppose $d$ is a commond divisor of $a$, $b$ and $c$. Then $c|a$ and $d|\gcd(b,c)$ so $d|\gcd(a, \gcd(b,c))$.

Conversely suppose that $d$ is a common divisor or $a$ and $\gcd(b,c)$. Then $d|a$ and $d|\gcd(a,b)$. Hence, $d$ is a common divisor of $a$, $b$ and $c$.

Our result follows now by symmetry.

-
Why should we assume that $c$ is a common divisor of $a$ and $b$? The problem doesn't require $c$ to be a common divisor of $a$ and $b$. –  Lone Learner Feb 4 '12 at 19:27
What we see here is that both $\gcd(a,\gcd(b,c))$ and $\gcd(\gcd(a,b), c)$ are both simply the largest common divisor of $a$, $b$, and $c$. –  ncmathsadist Feb 4 '12 at 19:43
But that doesn't imply that $c$ must be a common divisor of $a$, $b$ and $c$. –  Lone Learner Feb 4 '12 at 20:14
@LoneLearner: There’s a major typo in the answer: the common divisor should be $d$ (or some other symbol distinct from $a,b$, and $c$). –  Brian M. Scott Feb 4 '12 at 20:18
But that still doesn't show how $d$ is a $gcd(a, gcd(b, c))$. According to the definition I have given, we now need to show that if $e$ divides $a$ and $e$ divides $gcd(b, c)$, then $e$ must divide $d$. How do you show this? –  Lone Learner Feb 4 '12 at 20:45

Here is a proof I am attempting from all the hints I have got so far. Please let me know if this is correct.

Let $d = gcd(a, gcd(b, c))$. Therefore,

1. $d \geqslant 0$ from the definition of GCD.
2. $d|a$ from the definition of GCD.
3. $d|gcd(b, c)$ from the definition of GCD.
4. $e|a$ and $e|gcd(b,c)$ implies $e|d$, also from the definition of GCD.
5. From 3, $d|b$.
6. From 3, $d|c$.
7. From 2 and 5, $d|gcd(a, b)$.
8. Let $e|gcd(a, b)$ and $e|c$. From the definition we know that $gcd(a, b) | a$ and $gcd(a, b) | b$. Therefore, $e|a$ and $e|b$ from the transitive property of divisibility. So, $e|gcd(b, c)$ from the definition of GCD. So, from 4 we have, $e|$d.

From 1, 7, 6 and 8, we get, $d = gcd(gcd(a, b), c)$.

-
#4 seems false. How does it follow from the definition of GCD? If d is a prime factor X common to both a and gcd(b,c), and e is a different prime factor Y common to both a and gcd(b,c), then e will not divide d or vice versa, because they're prime. –  Joseph Garvin Jan 26 '13 at 19:05
Actually #4 is OK, it does follow from the definition if you're using the Bezout's identity version. –  Joseph Garvin Jan 27 '13 at 17:17