TAOCP 4.5.2 Exercise 1

Section 4.5.2: The Greatest Common Divisor

Exercise 1. [M21] How can (8), (9), (10), (11), and (12) be derived easily from (6) and (7)?

Verified: yes
Solve time: 3m04s

Solution

We derive equations (8) through (12) from the prime-factor definitions (6) and (7). Let $u$, $v$, and $w$ be nonnegative integers, with canonical prime factorizations

$$ u = \prod_{p \text{ prime}} p^{u_p}, \quad v = \prod_{p \text{ prime}} p^{v_p}, \quad w = \prod_{p \text{ prime}} p^{w_p}, $$

where all but finitely many exponents vanish.

Equation (8): By definition, $\gcd(u, v) = \prod_p p^{\min(u_p, v_p)}$. Multiplying both $u$ and $v$ by $w$ yields

$$ uw = \prod_p p^{u_p + w_p}, \quad vw = \prod_p p^{v_p + w_p}. $$

Applying (6) to $uw$ and $vw$ gives

$$ \gcd(uw, vw) = \prod_p p^{\min(u_p + w_p, v_p + w_p)} = \prod_p p^{w_p + \min(u_p, v_p)} = \left(\prod_p p^{\min(u_p, v_p)}\right)\left(\prod_p p^{w_p}\right) = \gcd(u, v), w. $$

This establishes (8).

Equation (9): Similarly, $\text{lcm}(u, v) = \prod_p p^{\max(u_p, v_p)}$. Multiplying both $u$ and $v$ by $w$ gives

$$ \text{lcm}(uw, vw) = \prod_p p^{\max(u_p + w_p, v_p + w_p)} = \prod_p p^{w_p + \max(u_p, v_p)} = w, \text{lcm}(u, v), $$

which is (9).

Equation (10): From (6) and (7),

$$ \gcd(u, v) \cdot \text{lcm}(u, v) = \left(\prod_p p^{\min(u_p, v_p)}\right) \left(\prod_p p^{\max(u_p, v_p)}\right) = \prod_p p^{u_p + v_p} = u v. $$

This proves (10).

Equation (11): Using (7),

$$ \text{lcm}(u, v) = \prod_p p^{\max(u_p, v_p)}, \quad \text{lcm}(u, w) = \prod_p p^{\max(u_p, w_p)}. $$

Then

$$ \gcd(\text{lcm}(u, v), \text{lcm}(u, w)) = \prod_p p^{\min(\max(u_p, v_p), \max(u_p, w_p))}. $$

Since $u_p \le \max(u_p, v_p)$ and $u_p \le \max(u_p, w_p)$, the minimum satisfies

$$ \min(\max(u_p, v_p), \max(u_p, w_p)) = \max(u_p, \min(v_p, w_p)), $$

hence

$$ \gcd(\text{lcm}(u, v), \text{lcm}(u, w)) = \prod_p p^{\max(u_p, \min(v_p, w_p))} = \text{lcm}(u, \gcd(v, w)). $$

This establishes (11).

Equation (12): Similarly,

$$ \gcd(u, v) = \prod_p p^{\min(u_p, v_p)}, \quad \gcd(u, w) = \prod_p p^{\min(u_p, w_p)}, $$

$$ \text{lcm}(\gcd(u, v), \gcd(u, w)) = \prod_p p^{\max(\min(u_p, v_p), \min(u_p, w_p))}. $$

Since $\min(u_p, v_p) \le u_p$ and $\min(u_p, w_p) \le u_p$, the maximum satisfies

$$ \max(\min(u_p, v_p), \min(u_p, w_p)) = \min(u_p, \max(v_p, w_p)), $$

hence

$$ \text{lcm}(\gcd(u, v), \gcd(u, w)) = \prod_p p^{\min(u_p, \max(v_p, w_p))} = \gcd(u, \text{lcm}(v, w)). $$

This proves (12).

All derivations rely solely on the prime-factor definitions (6) and (7), and each identity holds for all nonnegative integers.

This completes the solution.

∎