What is the general formula for Euler's totient function?

Conditions

• $n$ is a positive integer greater than 1.
• $p_1, \ldots, p_m$ are all the distinct prime factors of $n$.

Reasoning, step by step

1. Start with the prime factorization of $n$: $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$.
2. Use the multiplicativity of $\varphi$ to write $\varphi(n) = \varphi(p_1^{k_1}) \varphi(p_2^{k_2}) \cdots \varphi(p_m^{k_m})$.
3. Substitute the prime power formula $\varphi(p^k) = p^k - p^{k-1}$ for each factor.
4. Factor out $p_i^{k_i}$ from each term: $p_i^{k_i} - p_i^{k_i-1} = p_i^{k_i}(1 - 1/p_i)$.
5. Multiply all the factored terms together: $\varphi(n) = (p_1^{k_1} \cdots p_m^{k_m}) \prod_{i=1}^{m} (1 - 1/p_i)$.
6. Recognize that $p_1^{k_1} \cdots p_m^{k_m} = n$, yielding the final formula $\varphi(n) = n \prod_{i=1}^{m} (1 - 1/p_i)$.
7. Compress the product using product notation.

Example

For $n = 100$, the distinct prime factors are 2 and 5. Using the formula: $\varphi(100) = 100 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{5}\right) = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} = 40$.

Common misconceptions

• Including repeated prime factors in the product (the product is over DISTINCT prime factors).
• Forgetting to multiply by $n$ at the beginning of the formula.
• Confusing the general formula with the specific prime power formula $\varphi(p^k) = p^k - p^{k-1}$.

Watch the explanation

Explore next

• Why can $φ(p_1^{k_1}p_2^{k_2}\cdot \cdot \cdot p_m^{k_m})$ be split into $φ(p_1^{k_1})φ(p_2^{k_2})\cdot \cdot \cdot φ(p_m^{k_m})$?
• How is $φ(p^k) = p^k - p^{k-1}$ derived?
• What is the derivative of the upper limit u=sqrt(t) for $t>0$?