HMMT 二月 2007 · TEAM1 赛 · 第 3 题

英文解析

3. [ 25 ] Prove that for every integer n greater than 1,
   σ ( n ) φ ( n ) ≤ n − 1 .2
   When does equality hold?
   Solution. Note that
   2 2 2 2 2 2
   σ ( mn ) φ ( mn ) = σ ( m ) φ ( m ) σ ( n ) φ ( n ) ≤ ( m − 1)( n − 1) = ( mn ) − ( m + n − 1) < ( mn ) − 1
   for any pair of relatively prime positive integers ( m, n ) other than (1 , 1). Now, for p a prime and k a
   ( ) ( )
   k +1
   p − 1
   k k k k 1 k k − 1
   positive integer, σ p = 1 + p + · · · + p = and φ p = p − · p = ( p − 1) p . Thus,
   p − 1 pk +1
   ( ) ( )
   p − 1
   k k k − 1 k +1 k − 1 2 k k − 1 2 kσ p φ p = · ( p − 1) p = ( p − 1) p = p − p ≤ p − 1 ,
   p − 1
   with equality where k = 1. It follows that equality holds in the given inequality if and only if n isprime.