Past exam of the options I course of the University of Oxford / 2004 / C / C1 / a

By the fundamental theorem of arithmetic, every integer greater than one has a prime factorization, and that factorization is unique up to reordering the factors. Equivalently, it has a unique finite prime-exponent representation $\boxed{n=\prod _p{p}^{v_p(n)}}$, with nonnegative integer exponents. The unit integer has the empty product.

Write $a={\prod }_p{p}^{r_p}$ and $b={\prod }_p{p}^{s_p}$. Divisibility is exactly comparison of prime exponents. Thus the greatest common divisor uses $\min (r_p,s_p)$ and the least common multiple uses $\max (r_p,s_p)$. Since their sum is $r_p+s_p$ for each prime,