The Product Of The GCD And LCM

One way to prove this theorem is to use the factorization of each number into a product of primes. Some people call this the fundamental theorem of arithmetic, namely that each number can be written uniquely (up to reordering) as a product of prime numbers. As the proof follows directly from an example, let's look at one example.

Suppose $n=50=2^1\cdot3^0\cdot 5^2$ and $m=120 = 2^3\cdot 3^1 \cdot 5^1$. We list $3^0$ in the factorization of $n$ because this helps us see a general pattern. Since 2 appears once in the first number, and three times in the second, the greatest common divisor has one 2 in its factorization (the minimum of the powers 1 and 3). Also, any common multiple includes all three copies of 2 in its factorization (the maximum of the powers 1 and 3). Repeating this with each prime, we see that $\gcd(n,m) = 2^{\min\{1,3\}}\cdot 3^{\min\{0,1\}}\cdot 5^{\min\{2,1\}}$, and $\text{lcm}(m,n) = 2^{\max\{1,3\}}\cdot 3^{\max\{0,1\}}\cdot 5^{\max\{2,1\}}$. Since the sum of two numbers is equal to the sum of their minimum and maximum, the fact that $nm = \gcd(n,m)\text{lcm}(n,m)$ follows by using the commutative property of addition to rearrange the products of primes, as in $$\begin{align} nm &= \left(2^1\cdot3^0\cdot 5^2\right)\left(2^3\cdot 3^1 \cdot 5^1\right) \\ &= \underbrace{\left(2^1\cdot3^0\cdot 5^1\right)}_{\text{min exponents}}\underbrace{\left(2^3\cdot 3^1 \cdot 5^2\right)}_{\text{max exponents}} \\&= \gcd(n,m)\text{lcm}(n,m).\end{align}$$

The proof for general integers is similar. Suppose $n$ and $m$ are integers. After writing each number as a prime factorization, suppose that the distinct primes that appear in either integers are $p_1,p_2,\ldots, p_k$. We then write $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ and $m=p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}$. We then compute $$\begin{align} nm &= \left(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\right) \left(p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}\right) \\ &= \underbrace{\left(p_1^{\min\{a_1,b_1\}}p_2^{\min\{a_2,b_2\}}\cdots p_k^{\min\{a_k,b_k\}}\right)}_{\text{min exponents}}\underbrace{\left(p_1^{\max\{a_1,b_1\}}p_2^{\max\{a_2,b_2\}}\cdots p_k^{\max\{a_k,b_k\}}\right)}_{\text{max exponents}} \\ &= \gcd(n,m)\text{lcm}(n,m). \end{align}$$