HMMT 二月 2007 · TEAM1 赛 · 第 7 题
HMMT February 2007 — TEAM1 Round — Problem 7
题目详情
- [ 25 ] Show that for positive integers n , ∑ μ ( d ) φ ( n ) = . d n d | n
解析
- [ 25 ] Show that for positive integers n , ∑ μ ( d ) φ ( n ) = . d n d | n Solution. On the grounds of the previous problem, M¨ obius inversion with f ( k ) = φ ( k ) and g ( k ) = k gives: ( ) ( ) ∑ ∑ ∑ n n n ′ ′ φ ( n ) = f ( n ) = g ( d ) μ = g μ ( d ) = μ ( d ) . ′ ′ d d d ′ ′ d | n d | n d | n μ ( d ) Alternatively, one uses the convolution of the functions f ( k ) = n and g ( k ) = . The strategy is the d k k k − 1 same as the previous convolution proof. For n = p with k a positive integer, we have φ ( n ) = p − p , k k k k − 1 while the series reduces to p · μ (1) + p · μ ( p ) /p = p − p .