Show that $lcm$ is associative via nesting the maximum-function

Question

I found some proofs for the claim that for natural numbers $a,b,c$ it holds that $$ \operatorname{lcm}(\operatorname{lcm}(a,b),c) = \operatorname{lcm}(a,\operatorname{lcm}(b,c)). $$

I wonder whether one could show it this way: Let $\mathbb P$ be the set of prime numbers. Now let $$ a = \prod\limits_{p\in\mathbb P}p^{\alpha_p}, b = \prod\limits_{p\in\mathbb P}p^{\beta_p}, c = \prod\limits_{p\in\mathbb P}p^{\gamma_p} $$ be the unique prime decompositions. It is $$\operatorname{lcm}(a,b) = \prod\limits_{p\in\mathbb P}p^{\max\{\alpha_p, \beta_p\}}. $$

Then it is $$\operatorname{lcm}(\operatorname{lcm}(a,b),c) = \prod\limits_{p\in\mathbb P}p^{\max\{\max\{\alpha_p, \beta_p\},\gamma_p\}}. $$

And here I have the feeling I am missing an intermediate step, since nothing should be argumented with "it is obvious". So, am I maybe missing a valid argumented that these max relations can be nested this way?

Answer 1

My answer is written with the understanding that the question asks how to justify the nesting of $\text{max}\{.\}$ operators. In this case, the title should be changed.

If you let $L=\text{lcm}(a, b)$ and $$L=\prod_{p\in P}p^{\lambda_p}$$ where $\lambda_p=\text{max}\{\alpha_p, \beta_p\}$, you have: $$\text{lcm}\left(\text{lcm}(a, b), c\right)=\text{lcm}(L, c),$$ which is a stanadard LCM of two integers.

---

Furthermore, your nested $\{\text{max}\}$-es can be denested by observing the following:

Suppose you have the integers (or any real numbers really) $a$, $b$ and $c$ and you are interested in the value of $M=\text{max}\{\text{max}\{a, b\}, c\}$. Well, if $c$ is the largest of the three, clearly $M=\text{max}\{a, b, c\}=c$. Otherwise, $c$ is irrelevent and we can write: $$M=\text{max}\{\text{max}\{a, b\}, c\}=\text{max}\{a, b\}=\text{max}\{a, b, c\},$$ since $c<a$ or $c<b$.

Answer 2

Consider the set of positive integers, with partial order "$a$ divides $b$". Then "least upper bound" for that order is "greatest common divisor". If we prove this in the setting of a partially ordered set, using definition of "least upper bound", then we (a) get a more general result and (b) do not need "unique factorization".

In a partially ordered set, let $a \vee b$ denote the least upper bound of $\{a,b\}$ when it exists. We claim: if the four least upper bounds mentioned exist, then $$ a \vee (b\vee c) = (a\vee b)\vee c \tag1$$

Proof. Compute $$ a \le a \vee b \le (a\vee b)\vee c \tag2$$ Next $$ b \le (a\vee b)\le(a\vee b)\vee c\quad\text{and}\quad c\le (a\vee b)\vee c $$ so $$ b\vee c \le (a\vee b)\vee c \tag3$$ Note $(2)$ and $(3)$ say that $(a\vee b)\vee c$ is an upper bound for $\{a,b\vee c\}$, so it beats the least upper bound: $$ a \vee (b\vee c) \le (a\vee b)\vee c \tag4$$ Now we repeat this for the other direction. $$ a \le a \vee (b\vee c) \quad\text{and}\quad b \le (b\vee c) \le a \vee (b\vee c) $$ so $$ a\vee b \le a \vee (b\vee c) \tag5$$ and $$ c \le b\vee c \le a \vee (b\vee c) \tag6$$ From $(5)$ and $(6)$ we get $$ (a\vee b)\vee c \le a \vee (b\vee c) \tag7$$ Finally, from $(4)$ and $(7)$, we conclude $$ a \vee (b\vee c) = (a\vee b)\vee c \tag1$$