Proof That If n Is Odd, Then φ(2n) = φ(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 odd, then 2 is a not prime factor. This means if we multiply \(n\) by 2, then \(2n\) will have an extra prime factor:

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

Since \(2(1-\frac{1}{2}) = 1\):

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

Styles

(uses cookies)