HMMT 二月 2007 · TEAM1 赛 · 第 7 题

英文解析

7. [ 25 ] Show that for positive integers n ,
   ∑
   μ ( d ) φ ( n ) = .
   d nd | n
   Solution. On the grounds of the previous problem, M¨ obius inversion with f ( k ) = φ ( k ) and g ( k ) = kgives:
   ( ) ( )
   ∑ ∑ ∑
   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 thedk 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 .