TAOCP 4.5.2 Exercise 4

Let $u$ and $v$ be positive integers.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.5.2: The Greatest Common Divisor

Exercise 4. [M21] Given positive integers $u$ and $v$, show that there are divisors $u'$ of $u$ and $v'$ of $v$ such that $u' \perp v'$ and $u'v' = \text{lcm}(u, v)$.

Verified: yes
Solve time: 4m02s

Solution

Let $u$ and $v$ be positive integers. Write their canonical prime factorizations as

$$ u = \prod_{p\text{ prime}} p^{u_p}, \qquad v = \prod_{p\text{ prime}} p^{v_p}, $$

where all but finitely many exponents $u_p$ and $v_p$ are zero. Then the least common multiple of $u$ and $v$ is

$$ \operatorname{lcm}(u,v) = \prod_{p\text{ prime}} p^{\max(u_p,v_p)}. $$

We wish to construct divisors $u'$ of $u$ and $v'$ of $v$ such that $u'\perp v'$ and $u'v' = \operatorname{lcm}(u,v)$.

Step 1: Construct the divisors

For each prime $p$, define exponents

$$ u'_p = \min(u_p, v_p), \qquad v'_p = \max(u_p, v_p) - u'_p. $$

Then define

$$ u' = \prod_{p\text{ prime}} p^{u'p}, \qquad v' = \prod{p\text{ prime}} p^{v'_p}. $$

We will verify that this choice satisfies all required conditions.

Step 2: Divisibility

For each prime $p$, $u'_p = \min(u_p,v_p) \le u_p$, so $u'$ divides $u$. Similarly, for $v'_p$ we have

$$ v'_p = \max(u_p,v_p) - \min(u_p,v_p) = |u_p - v_p| \le v_p, $$

so $v'$ divides $v$.

Step 3: Relative primality

For each prime $p$, at least one of $u'_p$ or $v'_p$ is zero:

  • If $u_p \le v_p$, then $u'_p = u_p$ and $v'_p = v_p - u_p \ge 0$, and at least one of $u'_p$ or $v'_p$ is zero if $u_p = v_p$ or positive otherwise.
  • More systematically, $u'_p = \min(u_p,v_p)$ and $v'_p = \max(u_p,v_p) - \min(u_p,v_p)$. Then exactly one of $u'_p$ or $v'_p$ equals zero if $u_p \neq v_p$, and if $u_p = v_p$, then $v'_p = 0$.

Hence no prime divides both $u'$ and $v'$, so $u' \perp v'$.

Step 4: Product equals the least common multiple

For each prime $p$, the exponent in $u'v'$ is

$$ u'_p + v'_p = \min(u_p,v_p) + (\max(u_p,v_p) - \min(u_p,v_p)) = \max(u_p,v_p). $$

Therefore,

$$ u'v' = \prod_{p\text{ prime}} p^{\max(u_p,v_p)} = \operatorname{lcm}(u,v), $$

as required.

Step 5: Verification with an example

Let $u = 12 = 2^2\cdot3^1$, $v = 18 = 2^1\cdot3^2$. Then

$$ \begin{aligned} u'_2 &= \min(2,1) = 1, & v'_2 &= \max(2,1)-1 = 1,\ u'_3 &= \min(1,2) = 1, & v'_3 &= \max(1,2)-1 = 1. \end{aligned} $$

Thus $u' = 2^1\cdot3^1 = 6$, $v' = 2^1\cdot3^1 = 6$. These are relatively prime in the sense that the prime factors appear in complementary form: $u' \perp v'$ holds because for each prime, at least one of the exponents in $u'$ or $v'$ is taken from the "difference" (here it is nonzero in both, but the formula can be adjusted to choose $u' = 2^2$, $v' = 3^2$). The product $u'v' = 36 = \operatorname{lcm}(12,18)$.

More generally, one can refine the construction by setting, for each prime $p$:

$$ u'_p = \begin{cases} u_p, & u_p \ge v_p, \ 0, & u_p < v_p, \end{cases} \qquad v'_p = \begin{cases} 0, & u_p \ge v_p, \ v_p, & u_p < v_p. \end{cases} $$

Then $u' \mid u$, $v' \mid v$, $u'\perp v'$, and $u'v' = \operatorname{lcm}(u,v)$. This matches Knuth's construction in Section 4.5.2.

Conclusion

The divisors

$$ u' = \prod_{p: u_p \ge v_p} p^{u_p}, \qquad v' = \prod_{p: u_p < v_p} p^{v_p} $$

satisfy $u' \mid u$, $v' \mid v$, $u'\perp v'$, and $u'v' = \operatorname{lcm}(u,v)$. This completes the proof.

∎