Proof That If n Is Even, Then φ(2n) = 2φ(n)

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

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

If \(n\) is even, then 2 is a prime factor. Assume \(p_1 = 2\):

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

This means if we multiply \(n\) by 2:

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

This means:

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

Styles

(uses cookies)