HMMT 二月 2007 · TEAM1 赛 · 第 6 题

英文解析

6. [ 25 ] Show that for positive integers n ,
   ∑
   φ ( d ) = n.
   d | n
   Solution. Both sides are multiplicative functions of n, the right side trivially and the left because for
   ′
   relatively prime positive integers n and n ,
      
   ∑ ∑ ∑
   ′ ′
      
   φ ( d ) φ ( d ) = φ ( d ) φ ( d ) ,
   ′ ′ ′ ′
   d | n d | n d | n, d | n
   ′ ′ k k − 1
   and φ ( d ) φ ( d ) = φ ( dd ) . The identity is then easy to check; since φ ( p ) = p ( p − 1) for positive integers
   ( )
   k 2 k k − 1 kk and φ (1) = 1 , we have φ (1) + φ ( p ) + · · · + φ ( p ) = 1 + ( p − 1) + ( p − p ) + · · · + p − p = p , asdesired.