Proof That If m|n, Then φ(mn) = m * φ(n)

The formula for \(\phi(n)\) (derived here) is:

\[\phi(n) = n \prod_{i=1}^k \left( 1 - \frac{1}{p_i} \right)\]

If \(m|n\), then all prime factors that exist in \(m\) also exist in \(n\). This means:

\[\begin{align} \phi(mn) &= mn \prod_{i=1}^k \left( 1 - \frac{1}{p_i} \right) \\ &= m \ \phi(n) \end{align}\]

Styles

(uses cookies)