Show that

$\varphi(nm) = \gcd(n,m) \cdot \varphi( lcm(n,m) )$

where $\varphi(n)$ is equal to the number of integers between $0$ and $n-1$ that are relatively prime to n. In short, $\varphi(n) := \lvert \mathbb{Z_n^*} \rvert$. $\varphi$ is also known as the Euler's phi function.

== Attempt ==

In general, let $\{n_i\}_{i=1}^k$ be a pairwise relatively prime family of positive integers, and let $n := \prod_{i=1}^k n_i$. Then

$\varphi(n) = \prod_{i=1}^k \varphi(n_i)$

Furthermore, if $n = p_1^{e_1} \dotsm p_r^{e_r}$ is the factorization of $n$ into primes, then

$\varphi(n) = \prod_{i=1}^r p_i^{e_i-1}(p_i - 1) = n \prod_{i=1}^r (1 - \frac{1}{p_i})$

Let $d := \gcd(n,m)$, $n = n'd$ and $m = m'd$ for some integers $n', m'$. Then

$\varphi(nm) = \varphi(n'm'd^2) = \varphi(n'm') \cdot \varphi(d^2)$

as $\gcd(n'm', d^2) = 1$. Note that

$$\begin{aligned} \varphi(d) &= \prod_{i=1}^r p_i^{e_i-1} (p_i - 1) = d \prod_{i=1}^r (1 - \frac{1}{p_i}) \\ \varphi(d^2) &= \prod_{i=1}^r p_i^{2e_i-1} (p_i - 1) = d^2 \prod_{i=1}^r (1 - \frac{1}{p_i}) \\ \therefore \varphi(d^2) &= d \cdot \varphi(d) \\ \end{aligned}$$

Therefore,

$\varphi(nm) = \varphi(n'm') \cdot d \cdot \varphi(d) = d \cdot \varphi(n'm'd)$

as $\gcd(n'm', d) = 1$. But $n'm'd = lcm(n, m)$. So

$\varphi(nm) = d \cdot \varphi( lcm(n,m) ) = \gcd(n,m) \cdot \varphi( lcm(n,m) )$.

$\Box$