1
$\begingroup$

Let $x,y,z$ be positive integers such that \begin{align*}x &= \text{lcm}(\gcd(x,y),\gcd(z,x))\\ y &= \text{lcm}(\gcd(x,y),\gcd(y,z))\\ z&= \text{lcm}(\gcd(x,z),\gcd(y,z)).\end{align*} Prove that $\text{lcm}(x,y) = \text{lcm}(y,z) = \text{lcm}(x,z)= \text{lcm}(x,y,z)$.

Let the decomposition into primes of each of the variables be $x = \prod_{i}p_i^{\alpha_i},y = \prod_{i}p_i^{\beta_i},z = \prod_{i}p_i^{\gamma_i}$. Then $$x = \text{lcm}\left(\prod_{i}p_i^{\min(\alpha_i,\beta_i)},\prod_{i}p_i^{\min(\alpha_i,\gamma_i)}\right) = \prod_{i}p_i^{\max(\min(\alpha_i,\beta_i),\min(\alpha_i,\gamma_i))}$$ and we similarly obtain $y = \prod_{i}p_i^{\max(\min(\alpha_i,\beta_i),\min(\beta_i,\gamma_i))}$ and $z = \prod_{i}p_i^{\max(\min(\alpha_i,\gamma_i),\min(\beta_i,\gamma_i))}$. Therefore, $\text{lcm}(x,y) = \prod_{i}p_i^{\max(\max(\min(\alpha_i,\beta_i),\min(\alpha_i,\gamma_i)),\max(\min(\alpha_i,\beta_i),\min(\beta_i,\gamma_i)))}$ and similarly for the others.

Now we also must have $\alpha_i = \max(\min(\alpha_i,\beta_i),\min(\alpha_i,\gamma_i)),\beta_i = \max(\min(\alpha_i,\beta_i),\min(\beta_i,\gamma_i))$ and $\gamma_i = \max(\min(\alpha_i,\gamma_i),\min(\beta_i,\gamma_i))$. But I didn't see how to use these as conditions.

$\endgroup$
1
$\begingroup$

Suppose $\alpha_i < \beta_i < \gamma_i.$ Then, the last condition in your series fails. So, we must have $\beta_i = \gamma_i,$ while $\alpha_i \leq \beta_i.$ It is easy to see that the conclusion follows.

$\endgroup$
  • $\begingroup$ Could you elaborate? $\endgroup$ – user19405892 Jun 8 '17 at 1:59
  • $\begingroup$ $\gamma_i = \max(\min(\alpha_i,\gamma_i),\min(\beta_i,\gamma_i))= \max(\alpha_i, \beta_i).$ $\endgroup$ – Igor Rivin Jun 8 '17 at 2:01
  • $\begingroup$ How does the conclusion follow? Edit: Oh, so at least one of the two that are equal is guaranteed to be in the least common multiple. $\endgroup$ – user19405892 Jun 8 '17 at 2:08
  • $\begingroup$ @user19405892 The above max,min equation arises since min distributes over max. This distributivity holds more generally at the divisibility level, viz. gcd and lcm distribute over each other. Using that we can give a more general proof without using prime factorizations - see my answer. $\endgroup$ – Bill Dubuque Jun 8 '17 at 21:49
1
$\begingroup$

Write $\,[x,y] := {\rm lcm}(x,y),\, (x,y) :=\gcd(x,y).\ $ Note $\ x,y\mid [x,y,z]\,$ $\Rightarrow\,\color{#c00}{[x,y]\mid [x,y,z]}.\,$

For the reverse, $ $ since $ $ gcd distributes over lcm, $\ z = [(z,x),(z,y)] = (z,[x,y])\,$ $\Rightarrow\, z\mid [x,y],\,$ therefore this yields the $\rm\color{#0a0}{reverse}$ of the $\rm\color{#c00}{above}$ divisibility $\,x,y,z\mid [x,y]\,\Rightarrow\,\color{#0a0}{[x,y,z]\mid [x,y]}.\,$

Combining $\rm\color{#c00}{bo}\color{#0a0}{th}$ yields $\,[x,y] = [x,y,z]. \ $ By symmetry also $\,[y,z] = [x,y,z] = [z,x].$

Remark $ $ This proof is more general than one employing prime factorizations since it works in any gcd domain, i.e. any domain where gcds exists.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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