HMMT 二月 2007 · TEAM1 赛 · 第 10 题

英文解析

10. [ 40 ] Find all pairs ( n, k ) of positive integers such thatn 2
    σ ( n ) φ ( n ) = .
    Answer: ( 1 , 1 ) .k
    Solution. It is clear that for a given integer n, there is at most one integer k for which the equation
    2 2
    holds. For n = 1 this is k = 1. But, for n > 1 , problem 1 asserts that σ ( n ) φ ( n ) ≤ n − 1 < n , so thate e 2
    1 knk ≥ 2 . We now claim that 2 > . Write n = p · · · p , where the p are distinct primes and
    1 iσ ( n ) φ ( n ) ke ≥ 1 for all i, and let q < q < · · · be the primes in ascending order. Theni 1 2
    k k
    2 e 2 ei i 2
    ∏ ∏
    n p pi i = =
    e +1
    2 e e − 1
    i iip − 1
    σ ( n ) φ ( n ) e − 1
    i p − pii i
    · ( p − 1) pi =1 i =1
    p − 1 iiik k ∞
    ∏ ∏ ∏
    1 1 1 = ≤ <
    − 1 − e − 2 − 2
    1 − p 1 − p 1 − qii ii =1 i =1 i =1 i
     
    ∞ ∞ ∞
    ∏ ∑ ∑
    1 1
     
    = =
    2 jn 2
    i =1 j =0 n =1 iq
    (( ) ( ) ( ) )
    ∞
    ∑
    1 1 1 1 1 1 1 1 7 < 1 + = 1 + − + − + − + · · · = < 2 .
    n − 1 2 1 3 2 4 3 5 42
    n =2
    n 2
    It follows that there can be no solutions to k = other than n = k = 1 .
    σ ( n ) φ ( n )
    Grab Bag - Miscellaneous Problems [ 130 ] 4