HMMT 二月 2007 · TEAM1 赛 · 第 8 题

英文解析

8. [ 30 ] Determine with proof, a simple closed form expression for
   ( )
   ∑
   φ ( d ) τ .ndd | n
   Solution. We claim the series reduces to σ ( n ) . The series counts the ordered triples ( d, x, y ) withd | n ; x | d ; 0 < y ≤ n/d ; and ( y, n/d ) = 1 . To see this, write
   ( )
   ∑ ∑
   n n
   ′
   φ ( d ) τ = φ ( ) τ ( d ) ,
   ′
   d d
   ′
   d | n d | n
   ′
   so that for a given d | n we may choose x and y as described above. On the other hand, we can countnthese triples by groups sharing a given x. Fixing x as a divisor of n fixes an integer . Then d varies
   ( ) xn n n n nsuch that is a divisor of . For each divisor of there are precisely φ choices y , so that byd x d x dthe lemma from the previous problem, there are triples ( d, x, y ) for a given x. It follows that therenxare precisely σ ( n ) such triples ( d, x, y ) .
   Again, an alternative is to use the multiplicativity of the convolution, although it is now a little morekdifficult. Write n = p so thatk k
   ( )
   ∑ ∑ ∑
   ( )
   m k − m m − 1 nφ ( d ) τ = φ ( p ) τ p = k + 1 + p ( p − 1)( k − m + 1)
   m =0 m =1 dd | n
   ( ) ( )
   k k k − 1
   ∑ ∑ ∑
   ′
   m m − 1 k m = k + 1 + p ( k − m + 1) − p ( k − m + 1) = k + 1 + p − k + p
   ′
   m =1 m =1 m =1
   k k = 1 + p + · · · + p = σ ( p ) . 3