# Proof of associativity of GCD?

I am trying to demonstrate that

$$((a,b),c)=(a,(b,c))\qquad\text{ (Associativity of GCD)}.$$

My proof is the following:

Since $((a,b),c)|(a,b)$, $(a,b)|b$, $(a,b)|a$ and by transitivity we have $$((a,b),c)|b, ((a,b),c)|a.\tag{1}$$ We also have $((a,b),c)|c$.

By linearity we have $\forall x,y\in \mathbb{N}$ $$((a,b),c)|bx+cy.\tag{2}$$

We can choose $x$ and $y$ so that $$bx+cy=(b,c).\tag{3}$$

Therefore $((a,b),c)|(b,c)$ and $((a,b),c)|a$.

Again by linearity $$((a,b),c)|xa+y(b,c)\tag{4}$$ and we can choose $x$ and $y$ so that $$xa+y(b,c)=(a,(b,c)).\tag{5}$$

This mean $((a,b),c)|(a,(b,c))$.

Using an analogous argument we can show that $$(a,(b,c))|((a,b),c)$$ and by the reflexivity the thesis follows.

Is this correct?

• Maybe I am alone on this, but the formatting of your proof is really hard to read. I think I am getting old... – Cornman Oct 8 '17 at 10:40
• What's your definition of greatest common divisor? – egreg Oct 8 '17 at 10:51
• A number $d=ax+by$ such that $d\geq 0$ $d|a$ , $d|b$. Moreover if $e|a$ and $e|b$ imply $e|d$.@Cornman: you're right, it's not that easy to read. Sorry, i'll try to fix the format of my proof so that it'll be more readable. – Nikolaj Di Rondò Oct 8 '17 at 10:54
• @NikolajDiRondò With a little rewording, that makes $d$ the unique non-negative integer such that $\{\,ax+by\mid x,y\in\Bbb Z\,\}=d\Bbb Z$. You might then show that $(a,(b,c))$ (as well as by symmetry $((a,b),c)$) is the unique non-negative integer such that $\{\,ax+by+cz\mid x,y,z\in\Bbb Z\,\}=d\Bbb Z$. – Hagen von Eitzen Oct 8 '17 at 11:03

Your proof is correct, however, there is no need to invoke Bezout's identity. With doing so, you are using too much algebra, while what you are trying to prove is just a property of partial orders and is true in more general setting. It would be perhaps too strong of a statement to call it bad, but your proof doesn't generalize.

So, instead of doing $(2)$ the way you did, you can just say that since $((a,b),c)$ divides both $b$ and $c$, it must divide $(b,c)$ by the definition of the greatest common divisor. That's where the name comes from, if $d$ is a common divisor of $x$ and $y$, it divides $(x,y)$ since that's what the greatest means. The same thing applies to $(4)$ and $(5)$.

With this modification, you can write your proof like this:

$$((a,b),c)\mid(a,b),c \implies ((a,b),c)\mid a,b,c \implies ((a,b),c)\mid a,(b,c) \implies ((a,b),c)\mid(a,(b,c))\\ (a,(b,c))\mid a,(b,c) \implies (a,(b,c))\mid a,b,c \implies (a,(b,c))\mid (a,b),c \implies (a,(b,c))\mid((a,b),c)$$

and then conclude that $((a,b),c) = (a,(b,c))$ since division on $\mathbb N$ is antisymmetric.

So, what did I mean by more general setting? Well, $(\mathbb N,\,\mid\,)$ is partial order, i.e.

1. $a\mid a$ (reflexivity)
2. $a\mid b$ and $b\mid a$ implies $a = b$ (antisymmetry)
3. $a\mid b$ and $b\mid c$ implies $a\mid c$ (transitivity)

and greatest common divisor is the greatest lower bound or infimum of that partial order. So, given any partially ordered set $(P,\leq)$, you can use the same proof as above that $$\inf\{\inf\{a,b\},c\} = \inf\{a,\inf\{b,c\}\}$$ given that all of the infima exist. With a slight modification, you can also prove that $$\inf\{\inf\{a,b\},c\} = \inf\{a,b,c\} = \inf\{a,\inf\{b,c\}\}.$$

To round this up, define partial order $(\mathbb N, \preceq)$ with $a\preceq b$ if and only if $b\mid a$. The infimum of that partial order is what we usually cal the least common multiple, so we get that $$\operatorname{lcm}(\operatorname{lcm}(a,b),c) = \operatorname{lcm}(a,b,c) = \operatorname{lcm}(a,\operatorname{lcm}(b,c)).$$

Hopefully, I've managed to demonstrate why we like the proofs that generalize more than those that do not.

• Thank you Ennar, your answers is exactly what i was looking for. :) – Nikolaj Di Rondò Oct 8 '17 at 17:55

That's complicated .... Note that $d\mid(a,b)$ iff $d\mid a$ and $d\mid b$. So $d\mid((a,b),c)$ iff $d\mid (a,b)$ and $d\mid c$, that is if and only if $d\mid a$, $d\mid b$ and $d\mid c$. Similarly $d\mid(a,(b,c))$ iff $d\mid a$, $d\mid b$ and $d\mid c$. So $((a,b),c)$ and $(a,(b,c))$ are positive integers with the same divisors, so they must be equal.

• I know it's not the easiest way to demonstrate the associativity. Yours is much more simple. I was just trying to find an alternative proof. Is mine correct? – Nikolaj Di Rondò Oct 8 '17 at 11:17

Hint: use \begin{eqnarray*} GCD(p_1^{ \alpha_1} \cdots p_k^{ \alpha_k}, p_1^{ \beta_1} \cdots p_k^{ \beta_k} ) = p_1^{ \min(\alpha_1,\beta_1)} \cdots p_k^{ \min(\alpha_k,\beta_k)} \\ \end{eqnarray*} and $\min( \min( \alpha, \beta), \gamma)=\min(\alpha, \min (\beta,\gamma))$.