GCD and LCM from Prime Decomposition

Theorem

Let $m, n \in \Z$.

Let:

• $m = p_1^{k_1} p_2^{k_2} \ldots p_r^{k_r}$;
• $n = p_1^{l_1} p_2^{l_2} \ldots p_r^{l_r}$;
• $p_i \backslash m \lor p_i \backslash n, 1 \le i \le r$.

That is, the primes given in these decompositions may be divisors of either of the numbers $m$ or $n$.

Note that if one of the primes $p_i$ does not appear in the decompositions of either one of $m$ or $n$, then its corresponding index $k_i$ or $l_i$ will be zero.

Then the following results apply:

• $\gcd \left\{{m, n}\right\} = p_1^{\min \left\{{k_1, l_1}\right\}} p_2^{\min \left\{{k_2, l_2}\right\}} \ldots p_r^{\min \left\{{k_r, l_r}\right\}}$

• $\operatorname{lcm} \left\{{m, n}\right\} = p_1^{\max \left\{{k_1, l_1}\right\}} p_2^{\max \left\{{k_2, l_2}\right\}} \ldots p_r^{\max \left\{{k_r, l_r}\right\}}$

Proof

First we prove the result for the GCD:

Let $d \backslash m$. Now:

• $d$ is of the form $p_1^{h_1} p_2^{h_2} \ldots p_r^{h_r}, \forall i: 1 \le i \le r, 0 \le h_i \le k_i$.
• $d \backslash n \iff \forall i: 1 \le i \le r, 0 \le h_i \le l_i$

So $d \backslash m \land d \backslash n \iff \forall i: 1 \le i \le r, 0 \le h_i \le \min \left\{{k_i, l_i}\right\}$.

For $d$ to be at its greatest, we want the largest possible exponent for each of these primes.

So for each $i \in \left[{1 \, . \, . \, r}\right]$, $h_i$ needs to equal $\min \left\{{k_i, l_i}\right\}$.

Hence the result:

$\gcd \left\{{m, n}\right\} = p_1^{\min \left\{{k_1, l_1}\right\}} p_2^{\min \left\{{k_2, l_2}\right\}} \ldots p_r^{\min \left\{{k_r, l_r}\right\}}$

• We can get the corresponding result for the LCM by using this result:

Sum Less Minimum is Maximum: $a + b - \min \left\{{a, b}\right\} = \max \left\{{a, b}\right\}$.

We also make use of Product of GCD and LCM: $\operatorname{lcm} \left\{{a, b}\right\} \times \gcd \left\{{a, b}\right\} = \left|{a b}\right|$.

	\(\displaystyle \)	\(\displaystyle \operatorname{lcm} \left\{ {m, n}\right\}\)	\(=\)	\(\displaystyle \frac {m n} {\gcd \left\{ {m, n}\right\} }\)	\(\displaystyle \)	Product of GCD and LCM
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {\left({p_1^{k_1} p_2^{k_2} \ldots p_r^{k_r} }\right) \left({p_1^{l_1} p_2^{l_2} \ldots p_r^{l_r} }\right)} {p_1^{\min \left\{ {k_1, l_1}\right\} } p_2^{\min \left\{ {k_2, l_2}\right\} } \ldots p_r^{\min \left\{ {k_r, l_r}\right\} } }\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p_1^{k_1 + l_1 - \min \left\{ {k_1, l_1}\right\} } p_2^{k_2 + l_2 - \min \left\{ {k_2, l_2}\right\} } \ldots p_r^{k_r + l_r - \min \left\{ {k_r, l_r}\right\} }\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p_1^{\max \left\{ {k_1, l_1}\right\} } p_2^{\max \left\{ {k_2, l_2}\right\} } \ldots p_r^{\max \left\{ {k_r, l_r}\right\} }\)	\(\displaystyle \)	Sum Less Minimum is Maximum

So:

$\operatorname{lcm} \left\{ {m, n}\right\} = p_1^{\max \left\{ {k_1, l_1}\right\} } p_2^{\max \left\{ {k_2, l_2}\right\} } \ldots p_r^{\max \left\{ {k_r, l_r}\right\} }$

$\blacksquare$

Sources

• George E. Andrews: Number Theory (1971): $\S 2.4$: Exercises $5, \ 7$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 24 \alpha$