HMMT 二月 2021 · ALGNT 赛 · 第 5 题

HMMT February 2021 — ALGNT Round — Problem 5

Let n be the product of the first 10 primes, and let ∑ S = ϕ ( x ) · y, xy | n where ϕ ( x ) denotes the number of positive integers less than or equal to x that are relatively prime to x , and the sum is taken over ordered pairs ( x, y ) of positive integers for which xy divides n . Compute S . n

解析

Let n be the product of the first 10 primes, and let ∑ S = ϕ ( x ) · y, xy | n where ϕ ( x ) denotes the number of positive integers less than or equal to x that are relatively prime to x , and the sum is taken over ordered pairs ( x, y ) of positive integers for which xy divides n . Compute S . n Proposed by: Hahn Lheem Answer: 1024 Solution 1: We see that, for any positive integer n ,   ( ) ∑ ∑ ∑ ∑ n   S = ϕ ( x ) · y = ϕ ( x ) y = ϕ ( x ) σ . x n xy | n x | n y | x | n x Since ϕ and σ are both weakly multiplicative (if x and y are relatively prime, then ϕ ( xy ) = ϕ ( x ) ϕ ( y ) and σ ( xy ) = σ ( x ) σ ( y )), we may break this up as ∏ ( ϕ ( p ) + σ ( p )) , p 10 10 where the product is over all primes that divide n . This is simply 2 n , giving an answer of 2 = 1024. Solution 2: We recall that ∑ ϕ ( d ) = n. d | n So, we may break up the sum as ( ) ∑ ∑ ∑ ∑ n S = ϕ ( x ) · y = y ϕ ( x ) = y , y n xy | n y | n x | y | n y 10 so S is simply n times the number of divisors of n . This number is 2 = 1024. Solution 3: When constructing a term in the sum, for each prime p dividing n , we can choose to include p in x , or in y , or in neither. This gives a factor of p − 1, p , or 1, respectively. Thus we can factor the sum as ∏ ∏ 10 S = ( p − 1 + p + 1) = 2 p = 2 n. p | n p | n So the answer is 1024.