6
$\begingroup$

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?

  • 5
    Show that both sides equal gcd(a,b,c).2012-02-04
  • 2
    I haven't encountered the definition of gcd of three numbers in the text yet and I am trying to avoid it.2012-02-04
  • 1
    [Proof that GCD is associative](http://zimmer.csufresno.edu/~larryc/proofs/proofs.unwinding.html)2012-02-04
  • 1
    @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.2012-02-04
  • 0
    ....and that works just as well for four sets, or five sets, or any other number.2012-02-04
  • 0
    There's an argument similar to what I outlined above that shows that the gcd of no numbers at all is $0.$ But the question posted here suggests another way to show that: Taking the value of an operation applied to no arguments to be the identity element makes sense precisely when the operation is _associative_.2012-02-04
  • 0
    But maybe what I just said doesn't work: the intersection of no sets at all should be the "universe".2012-02-04
  • 1
    By considering prime factorizations, it's a consequence of $\min(x,\min(y,z)) = \min(\min(x,y),z)$.2012-02-05

4 Answers 4

0

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

  • 0
    #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.2013-01-26
  • 0
    Actually #4 is OK, it does follow from the definition if you're using the Bezout's identity version.2013-01-27
20

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

  • 0
    nice hint! (+1)2012-02-04
  • 0
    +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\;$.2013-07-26
3

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.

  • 0
    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?2012-02-04
  • 0
    @Lone Learner: It is inconvenient to work with $d$ directly, it is clearer to work with any common divisor.2012-02-04
  • 0
    @AndréNicolas I think you have only proved that $u$ is a common divisor. What about the GCD?2016-03-05
  • 0
    @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)2016-03-05
  • 0
    (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$.2016-03-05
1

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.

  • 1
    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$.2012-02-04
  • 0
    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$.2012-02-04
  • 0
    But that doesn't imply that $c$ must be a common divisor of $a$, $b$ and $c$.2012-02-04
  • 2
    @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$).2012-02-04
  • 0
    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?2012-02-04
  • 0
    @LoneLearner: The proof shows that the *set* of common divisors of $a$ and $\gcd(b,c)$ is the *same* as the *set* of common divisors of $\gcd(a,b)$ and $c$. In particular, $\gcd(a,\gcd(b,c))$ must divide both $\gcd(a,b)$ and $c$, hence must divide $\gcd(\gcd(a,b),c)$); and *conversely*, $\gcd(\gcd(a,b),c)$ must divide both $a$ and $\gcd(b,c)$, hence must divide $\gcd(a,\gcd(b,c))$. Since the two gcds divide each other and are both positive, they must be equal.2012-02-04
  • 0
    How do we know c divides a in the third sentence?2013-01-26