Why is true that $\operatorname{lcm}(\gcd(c_1,c_3),\gcd(c_2,c_3))=\gcd(\operatorname{lcm}(c_1,c_2),c_3)$ ?

LHS is $\displaystyle\frac{\gcd(c_1,c_3)\gcd(c_2,c_3)}{\gcd(c_1,c_2,c_3)}$

RHS is $\displaystyle\gcd\left(\frac{c_1c_2}{\gcd(c_1,c_2)},c_3\right)$

Since $c_1$ and $\frac{c_2}{\gcd(c_1,c_2)}$ are coprime, I can use the distributive property and write RHS as


So if I compare both formula and cancel $\gcd(c_1,c_3)$ from both sides, the following must hold


It seems, that I obtained a more complicated equality to prove


$\newcommand{\lcm}[0]{\mathrm{lcm}}$The proof of $$ \gcd(\lcm(c_{1}, c_{2}), c_{3}) = \lcm(\gcd(c_{1}, c_{3}), \gcd(c_{2}, c_{3})). $$ is arguably best done using the formula for the gdc and lcm in terms of factorization as product of prime powers. That is, if $p_{k}$ are distinct primes, and $$ c_{i} = \prod_{k} p_{k}^{f_{ik}}, $$ then $$ \gcd(c_{i}, c_{j}) = \prod_{k} p_{k}^{\min(f_{ik}, f_{jk})}, \quad\text{and}\quad \lcm(c_{i}, c_{j}) = \prod_{k} p_{k}^{\max(f_{ik}, f_{jk})}. $$

This way you see immediately that you can reduce to the case when all $c_{i}$ are power of the same prime $p$, that is, $c_{i} = p^{e_{i}}$ for some $e_{i}$.

Now this is easily seen to boil down to the fact that max and min distribute with respect to each other, in particular for this case $$ \min(\max(e_{1}, e_{2}), e_{3}) = \max(\min(e_{1}, e_{3}), \min(e_{2}, e_{3})). $$ This you deal with just distinguishing the $3$ possible cases (noting the symmetry between $e_{1}$ and $e_{2}$) for the relative ordering of the $e_{i}$.


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.