TAOCP 4.5.2 Exercise 3
Let n=\prod_{p}p^{a_p} be the canonical factorization of $n$, as in (5), where only finitely many exponents $a_p$ are nonzero.
Section 4.5.2: The Greatest Common Divisor
Exercise 3. [M23] Show that the number of ordered pairs of positive integers $(u, v)$ such that $\text{lcm}(u, v) = n$ is the number of divisors of $n^2$.
Verified: yes
Solve time: 1m15s
Solution
Let
$$ n=\prod_{p}p^{a_p} $$
be the canonical factorization of $n$, as in (5), where only finitely many exponents $a_p$ are nonzero.
Suppose that
$$ u=\prod_{p}p^{b_p}, \qquad v=\prod_{p}p^{c_p}, $$
with $0\le b_p,c_p\le a_p$ for every prime $p$. By (7),
$$ \operatorname{lcm}(u,v) = \prod_{p}p^{\max(b_p,c_p)}. $$
Therefore the condition
$$ \operatorname{lcm}(u,v)=n $$
is equivalent to
$$ \max(b_p,c_p)=a_p \qquad\text{for every prime }p. $$
Fix a prime $p$ with exponent $a=a_p$. We must count the ordered pairs $(b,c)$ satisfying
$$ 0\le b,c\le a, \qquad \max(b,c)=a. $$
There are $(a+1)^2$ pairs with $0\le b,c\le a$. Among them, exactly $a^2$ pairs satisfy $b<a$ and $c<a$. Hence the number satisfying $\max(b,c)=a$ is
$$ (a+1)^2-a^2=2a+1. $$
The choices for distinct primes are independent, so the number of ordered pairs $(u,v)$ with $\operatorname{lcm}(u,v)=n$ is
$$ \prod_{p}(2a_p+1). $$
Now consider $n^2$:
$$ n^2=\prod_{p}p^{2a_p}. $$
The number of positive divisors of $n^2$ is obtained by choosing, for each prime $p$, an exponent between $0$ and $2a_p$. Thus the divisor count is
$$ \prod_{p}(2a_p+1). $$
This is exactly the number obtained above. Therefore the number of ordered pairs of positive integers $(u,v)$ such that
$$ \operatorname{lcm}(u,v)=n $$
is equal to the number of divisors of $n^2$.
$$ \boxed{#{(u,v):\operatorname{lcm}(u,v)=n}=d(n^2)} $$
where $d(m)$ denotes the number of positive divisors of $m$.
This completes the proof.
∎