HMMT 二月 2007 · TEAM1 赛 · 第 3 题

HMMT February 2007 — TEAM1 Round — Problem 3

[ 25 ] Prove that for every integer n greater than 1, 2 σ ( n ) φ ( n ) ≤ n − 1 . When does equality hold? 1

解析

[ 25 ] Prove that for every integer n greater than 1, 2 σ ( n ) φ ( n ) ≤ n − 1 . 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 p k +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 is prime.