HMMT 二月 2007 · TEAM1 赛 · 第 6 题
HMMT February 2007 — TEAM1 Round — Problem 6
题目详情
- [ 25 ] Show that for positive integers n , ∑ φ ( d ) = n. d | n
解析
- [ 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 k k and φ (1) = 1 , we have φ (1) + φ ( p ) + · · · + φ ( p ) = 1 + ( p − 1) + ( p − p ) + · · · + p − p = p , as desired.