GCD and LCM Distribute Over Each Other

Theorem

Let $a, b, c \in \Z$.

Then:

• $\operatorname{lcm} \left\{{a, \gcd \left\{{b, c}\right\}}\right\} = \gcd \left\{{\operatorname{lcm} \left\{{a, b}\right\}, \operatorname{lcm} \left\{{a, c}\right\}}\right\}$;
• $\gcd \left\{{a, \operatorname{lcm} \left\{{b, c}\right\}}\right\} = \operatorname{lcm} \left\{{\gcd \left\{{a, b}\right\}, \gcd \left\{{a, c}\right\}}\right\}$.

That is, greatest common divisor and lowest common multiple are distributive over each other.

Proof

• We show that lowest common multiple is distributive over greatest common divisor.

Let $p_s$ be any of the prime divisors of $a, b$ or $c$, and let $s_a, s_b$ and $s_c$ be its exponent in each of those numbers.

Let $x = \operatorname{lcm} \left\{{a, \gcd \left\{{b, c}\right\}}\right\}$.

Then from GCD and LCM from Prime Decomposition, the exponent of $p_s$ in $x$ is $\max \left\{{s_a, \min \left\{{s_b, s_c}\right\}}\right\}$.

From Max and Min Distributive, $\max$ distributes over $\min$.

Therefore $\max \left\{{s_a, \min \left\{{s_b, s_c}\right\}}\right\} = \min \left\{{\max \left\{{s_a, s_b}\right\}, \max \left\{{s_a, s_c}\right\}}\right\}$ and the result follows.

• The same argument can be used to show that greatest common divisor is distributive over lowest common multiple, except this time using the result from Max and Min Distributive that $\min$ distributes over $\max$.

$\blacksquare$

Sources

• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 23 \epsilon$