HMMT 二月 2007 · TEAM1 赛 · 第 8 题

HMMT February 2007 — TEAM1 Round — Problem 8

[ 30 ] Determine with proof, a simple closed form expression for ( ) ∑ n φ ( d ) τ . d d | n

解析

[ 30 ] Determine with proof, a simple closed form expression for ( ) ∑ n φ ( d ) τ . d d | n Solution. We claim the series reduces to σ ( n ) . The series counts the ordered triples ( d, x, y ) with d | 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 count n these triples by groups sharing a given x. Fixing x as a divisor of n fixes an integer . Then d varies ( ) x n n n n n such that is a divisor of . For each divisor of there are precisely φ choices y , so that by d x d x d n the lemma from the previous problem, there are triples ( d, x, y ) for a given x. It follows that there x are precisely σ ( n ) such triples ( d, x, y ) . Again, an alternative is to use the multiplicativity of the convolution, although it is now a little more k difficult. Write n = p so that k k ( ) ∑ ∑ ∑ ( ) n m k − m m − 1 φ ( d ) τ = φ ( p ) τ p = k + 1 + p ( p − 1)( k − m + 1) d m =0 m =1 d | 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