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\)