HMMT 二月 2016 · 冲刺赛 · 第 31 题
HMMT February 2016 — Guts Round — Problem 31
题目详情
- [ 16 ] For a positive integer n , denote by τ ( n ) the number of positive integer divisors of n , and denote by φ ( n ) the number of positive integers that are less than or equal to n and relatively prime to n . Call a positive integer n good if ϕ ( n ) + 4 τ ( n ) = n . For example, the number 44 is good because ϕ (44) + 4 τ (44) = 44. Find the sum of all good positive integers n . √
解析
- [ 16 ] For a positive integer n , denote by τ ( n ) the number of positive integer divisors of n , and denote by φ ( n ) the number of positive integers that are less than or equal to n and relatively prime to n . Call a positive integer n good if ϕ ( n ) + 4 τ ( n ) = n . For example, the number 44 is good because ϕ (44) + 4 τ (44) = 44. Find the sum of all good positive integers n . Proposed by: Lawrence Sun Answer: 172 We claim that 44 , 56 , 72 are the only good numbers. It is easy to check that these numbers work. Now we prove none others work. First, remark that as n = 1 , 2 fail so we have ϕ ( n ) is even, thus n is √ √ even. This gives us ϕ ( n ) ≤ n/ 2. Now remark that τ ( n ) < 2 n , so it follows we need n/ 2 + 8 n > n = ⇒ n ≤ 256. This gives us a preliminary bound. Note that in addition we have 8 τ ( n ) > n . a b Now, it is easy to see that powers of 2 fail. Thus let n = 2 p where p is an odd prime. From 1 1 a b a b 8 τ ( n ) > n we get 8( a + 1)( b + 1) > 2 p ≥ 2 3 from which we get that ( a, b ) is one of 1 (1 , 1) , (1 , 2) , (1 , 3) , (2 , 1) , (2 , 2) , (3 , 1) , (3 , 2) , (4 , 1) . √ b 8( a +1)( b +1) Remark that p ≤ . From this we can perform some casework: 1 a 2 • If a = 1 , b = 1 then p − 1 + 16 = 2 p but then p = 15, absurd. 1 1 • If a = 1 , b = 2 then we have p ≤ 5 which is obviously impossible. 1 • If a = 1 , b = 3 then p ≤ 4 which is impossible. 1 • If a = 2 , b = 1 then p ≤ 12 and it is easy to check that p = 11 and thus n = 44 is the only 1 1 solution. • If a = 2 , b = 2 then p ≤ 4 which is impossible. 1 • If a = 3 , b = 1 then p ≤ 8 and only p = 7 or n = 56 works. 1 1 • If a = 3 , b = 2 then p ≤ 3 and p = 3 , n = 72 works. 1 1 • If a = 4 , b = 1 then p ≤ 1 which is absurd. 1 a b c Now suppose n is the product of 3 distinct primes, so n = 2 p p so we have 8( a + 1)( b + 1)( c + 1) > 1 2 a b c 2 3 5 then we must have ( a, b, c ) equal to one of (1 , 1 , 1) , (1 , 2 , 1) , (2 , 1 , 1) , (3 , 1 , 1) . Again, we can do some casework: • If a = b = c = 1 then 8 τ ( n ) = 64 > 2 p p but then p = 3 , p = 5 or p = 3 , p = 7 is forced 1 2 1 2 1 2 neither of which work. 2 • If a = 1 , b = 2 , c = 1 then 8 τ ( n ) = 96 > 2 p p but then p = 3 , p = 5 is forced which does not 2 1 2 1 work. • If a = 2 , b = 1 , c = 1 then 8 τ ( n ) = 96 > 4 p p forces p = 3 , p = 5 or p = 3 , p = 7 neither of 1 2 1 2 1 2 which work. • If a = 3 , b = 1 , c = 1 then 8 τ ( n ) = 108 > 8 p p which has no solutions for p , p . 1 2 1 2 Finally, take the case where n is the product of at least 4 distinct primes. But then n ≥ 2 · 3 · 5 · 7 = 210 and as 2 · 3 · 5 · 11 > 256, it suffices to check only the case of 210. But 210 clearly fails, so it follows that 44 , 56 , 72 are the only good numbers so we are done. √