HMMT 二月 2016 · 冲刺赛 · 第 31 题

英文解析

31. [ 16 ] For a positive integer n , denote by τ ( n ) the number of positive integer divisors of n , and denoteby φ ( 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. Froma b a b 11
    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 , 2) , (1 , 3) , (2 , 1) , (2 , 2) , (3 , 1) , (3 , 2) , (4 , 1) .1
    √
    b 8( a +1)( b +1)
    Remark that p ≤ . From this we can perform some casework:
    1 a
    • If a = 1 , b = 1 then p − 1 + 16 = 2 p but then p = 15, absurd.2
    1 1
    • If a = 1 , b = 2 then we have p ≤ 5 which is obviously impossible.
    • 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 1
    solution.
    • If a = 2 , b = 2 then p ≤ 4 which is impossible.
    • If a = 3 , b = 1 then p ≤ 8 and only p = 7 or n = 56 works.1
    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.
    a b c 1
    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.
    • 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
    2 1 2
    work.1
    • 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 followsthat 44 , 56 , 72 are the only good numbers so we are done.
    √