# 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.

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 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
@AndréNicolas I think you have only proved that $u$ is a common divisor. What about the GCD? – Dhruv Mar 5 at 16:08
@DhruvSomani: Let $X$ be the LHS, and $Y$ the RHS. The proof above shows that every divisor of $X$ is a divisor of $Y$. (The fact that every divisor of $Y$ is a divisor of $X$ was mentioned in the last sentence, but not proved since the proof is essentially the same as the proof that every divisor of $X$ is a divisor of $Y$.) If two positive numbers have the same set of divisors, they are the same, so the result follows. (More) – André Nicolas Mar 5 at 17:19
(More) I did not prove that if two positive numbers have the same set of divisors they are the same, but this is easy. Note that $X$ divides $X$ so by the proof in the post $X$ divides $Y$. Similarly $Y$ divides $X$. So $X\le Y$ and $Y\le X$. – André Nicolas Mar 5 at 17:20

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