I want to solve the following problem:
Prove that if $m$, $n$ $\in \mathbb {N}$ with $g=\gcd(m, n)$, then $$\phi(mn) = \frac{g\phi(m)\phi(n)}{\phi(g)}$$
I know I want to use the multiplicative property of the $\phi$-function that $\phi(mn)=\phi(m)\phi(n)$, for any $m$, $n$ $\in \mathbb {N}$ which are relatively prime. I understand how this works: if $g =1$, i.e. if $\gcd(m, n)=1$, then $$\frac{g}{\phi(g)} = \frac{1}{1}$$
This would of course give me the easy case that when $\gcd(m, n) = 1$, $\phi(mn)=\phi(m)\phi(n)$.
What's throwing me off is how to prove the more general result when $m$ and $n$ are not coprime.
Best Answer
You might want to use the general formula $$ \varphi(n) = n \prod_{p \, | \, n} \left( 1 - \frac 1p \right) $$ where the product is taken over all primes dividing $n$. Then you get $$ \varphi(mn) = mn \prod_{p \, | \, mn} \left( 1 - \frac 1p \right) = \frac{ \left( m \prod_{p \, | \, m} \left( 1 - \frac 1p \right) \right)\left( n \prod_{p \, | \, n} \left( 1 - \frac 1p \right) \right) }{\prod_{p \, | \, g} \left( 1 - \frac 1p \right)} $$ and since the numerator is precisely $\varphi(g)/g$, you are done.
Note that this formula for $\varphi(n)$ can be computed using the multiplicative property of $\varphi(n)$, together with $\varphi(p^{\alpha}) = p^{\alpha-1}(p-1)$ for a prime $p$ and a positive integer $\alpha > 0$.
Hope that helps,