PUMaC 2021 · 数论（A 组） · 第 6 题

PUMaC 2021 — Number Theory (Division A) — Problem 6

Let f ( n ) = . Find the sum of all positive integers n for which f ( n ) = 6 . i =1 n

解析

Let f ( n ) = . Find the sum of all n so that f ( n ) = 6 . i =1 n Proposed by: Frank Lu Answer: 1192 Note that, the number of i so that gcd( i, n ) = d is ϕ ( n/d ) , if n | d . Then, we see that P P P n f ( n ) = gcd( i, n ) = dϕ ( n/d ) = n/dϕ ( d ) Now, suppose that n has prime i =1 d | n d | n e e 1 1 k factorization n = p . . . p . Then, note that, since ϕ ( d ) is multiplicative, we can write 1 k d Q P Q P Q P k e k e k e j j − 1 p − 1 i i i 1 1 i f ( n ) /n as ϕ ( p ) = (1 + p ( p − 1)) = (1 + ) = j j i =1 j =0 i i =1 j =1 i i =1 j =1 p i p p i i Q Q k e ( p − 1) k ( e +1) p − e i i i i i (1 + ) . = ( ) . Now, for this to be even, we need that the numerator i =1 i =1 p p i i of this product to first be even. But note that for p odd that ( e +1) p − e is odd, which means i i i i that one of our primes has to be 2 , which say is p = 2 . Furthermore, we need that e / 2 + 1 1 1 needs to be even for the product to equal 6 . We thus see that e = 2 , 6 , 10 . For e = 10 , we see 1 1 10 that we just have one prime factor, which means that we get the number n = 2 = 1024 . For e = 6 , we have that e / 2 + 1 = 4 , which is too small. However, note also that the smallest 1 1 possible value for any other term in the product, with p ≥ 3 , is 5 / 3 > 3 / 2 . For e = 2 , we i 1 have that e / 2 + 1 = 2 , again is too small. We want the product of the next terms to be 1