HMMT 二月 2026 · 冲刺赛 · 第 29 题
HMMT February 2026 — Guts Round — Problem 29
题目详情
- [16] Compute ( ) 4004 ∑ πk gcd( k, 4004) cos . 2002 k =1
解析
- [16] Compute ( ) 4004 ∑ πk gcd( k, 4004) cos . 2002 k =1 Proposed by: Jacopo Rizzo Answer: 1440 ©2026 HMMT Solution 1: More generally, we claim that ( ) n ∑ 2 πk gcd( k, n ) cos = φ ( n ) n k =1 from which plugging in n = 4004 gives 1440 . To prove the claim, we first note that the sum is the real part of n ∑ k gcd( k, n ) ζ , k =0 ∑ 2 πi/n where ζ = e is the n -th root of unity. To evaluate this, we use φ ( d ) = n to get that d | n n n ∑ ∑ ∑ k k gcd( k, n ) ζ = φ ( d ) ζ k =1 k =1 d | gcd( k,n ) n ∑ ∑ k = φ ( d ) ζ k =1 d | k and d | n n d ∑ ∑ dt = φ ( d ) ζ . t =1 d | n If d = n , then the inner sum is 1 . Otherwise, by geometric series, the inner sum is d · n/d ζ ( ζ − 1) = 0 . d ζ − 1 ∑ n k This establishes that gcd( k, n ) ζ = φ ( n ) . k =1 2 πi/n k − k Solution 2: Let n = 4004 and ζ = e , so that 2 cos( πk/ 2002) = ζ + ζ . 2 πi/n Claim 1. If ω = e , then ∑ k g ( n ) := ω = μ ( n ) . gcd( k,n )=1 , 0 ≤ k<n Proof. The function n ∑ 2 πik/n f ( n ) = e k =0 is 0 when n > 1 , and 1 when n = 1 . On the other hand, by considering gcd( k, n ) (e.g. primitive d th roots of unity for d | n ) we see ∑ f ( n ) = g ( d ) . d | n But this readily implies g ( n ) = μ ( n ) by mobius inversion, as desired. ©2026 HMMT We can now calculate: ( ) ( ) n n n k − k k − k ∑ ∑ ∑ ζ + ζ ζ ζ gcd( k, n ) = gcd( k, n ) + gcd( k, n ) 2 2 2 k =1 k =1 k =1 ( ) ( ) ′ n n k n − k ∑ ∑ ζ ζ ′ = gcd( k, n ) + gcd( n − k , n − 1) 2 2 ′ k =1 k =0 n ∑ k = gcd( k, n ) ζ k =1 ∑ ∑ k = d ζ d | n gcd( k,n )= d ∑ ∑ d j = d ( ζ ) d | n gcd( j,n/d )=1 ∑ = dμ ( n/d ) d | n = φ ( n ) . Plugging in n = 4004 gives φ (4004) = 1440 .