If $n=p_1^{a_1}p_2^{a_2}...p_l^{a_l}$, then $\phi(n)=n(1-1/p_1)(1-1/p_2)...(1-1/p_l)$

Proof: Since $n=\sum_{d|n}\phi(n)$, Mobius inversion thm implies $$\phi(n)=\sum_{d|n}\mu(n){n\over d}=n-\sum_in/p_i+\sum_{i\lt j}{n\over p_ip_j}-...=n(1-1/p_1)(1-1/p_2)...(1-1/p_l)$$

I don't know how to convert all the summations into products. Any hint?

Thank you!


If $f(n) = \sum_{d | n} g(d)$ is multiplicative then $g(n)=\sum_{d | n} \mu(d) f(n/d)$ is multiplicative.

Here $f(n) = n, g(n) =\phi(n)$. Multiplicative-ness means that $$g(n) = \prod_{p^k \| n} g(p^k) = \prod_{p^k \| n} (p^k - p^{k-1}) =\prod_{p^k \| n} p^k (1 - \frac{1}{p}) = n\prod_{p^k \| n} (1 - \frac{1}{p})$$ (where $p^k \| n$ means $p$ is prime, $p^k | n$ and $p^{k+1} \nmid n$)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.