8
$\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?

  • 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

1

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

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
    +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
4

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

  • 0
    How do we know$c$divides$a$in the third sentence?2013-01-26