TAOCP 4.5.2 Exercise 2

Exercise 2. [M22] Given that $u$ divides $v_1 v_2 \ldots v_n$, prove that $u$ divides

$$\gcd(u, v_1), \gcd(u, v_2) \ldots \gcd(u, v_n).$$

Verified: yes
Solve time: 1m15s

Solution

Let

$$ u=\prod_{p} p^{u_p}, \qquad v_i=\prod_{p} p^{v_{i,p}} \quad (1\le i\le n) $$

be the canonical prime factorizations of the positive integers involved, as in equation (5). Since

$$ u\mid v_1v_2\cdots v_n, $$

comparison of prime exponents gives

$$ u_p\le \sum_{i=1}^{n} v_{i,p} \qquad\text{for every prime }p. \tag{13} $$

By equation (6),

$$ \gcd(u,v_i) = \prod_{p} p^{\min(u_p,v_{i,p})}. $$

Hence

$$ \prod_{i=1}^{n}\gcd(u,v_i) = \prod_{p} p^{\sum_{i=1}^{n}\min(u_p,v_{i,p})}. \tag{14} $$

To prove that $u$ divides this product, it suffices to show that for every prime $p$,

$$ u_p \le \sum_{i=1}^{n}\min(u_p,v_{i,p}). \tag{15} $$

Fix a prime $p$.

If some $v_{i,p}\ge u_p$, then

$$ \sum_{i=1}^{n}\min(u_p,v_{i,p}) \ge \min(u_p,v_{i,p}) = u_p, $$

so (15) holds.

Otherwise $v_{i,p}<u_p$ for all $i$. Then

$$ \min(u_p,v_{i,p})=v_{i,p}, $$

and therefore

$$ \sum_{i=1}^{n}\min(u_p,v_{i,p}) = \sum_{i=1}^{n}v_{i,p} \ge u_p $$

by (13). Thus (15) also holds in this case.

Consequently, for every prime $p$, the exponent of $p$ in the factorization (14) is at least $u_p$. Therefore

$$ \prod_{i=1}^{n}\gcd(u,v_i) = \prod_{p} p^{\sum_{i=1}^{n}\min(u_p,v_{i,p})} = u\cdot \prod_{p} p^{\sum_{i=1}^{n}\min(u_p,v_{i,p})-u_p}, $$

and the second factor is an integer. Hence

$$ u \mid \gcd(u,v_1),\gcd(u,v_2)\cdots\gcd(u,v_n). $$

This completes the proof.

∎