Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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*}$$

share|cite|improve this answer
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.

share|cite|improve this answer
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.

share|cite|improve this answer
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
up vote 0 down vote accepted

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

share|cite|improve this answer
#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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.