HMMT 二月 2007 · TEAM1 赛 · 第 10 题

HMMT February 2007 — TEAM1 Round — Problem 10

[ 40 ] Find all pairs ( n, k ) of positive integers such that 2 n σ ( n ) φ ( n ) = . k Grab Bag - Miscellaneous Problems [ 130 ]

解析

[ 40 ] Find all pairs ( n, k ) of positive integers such that 2 n σ ( n ) φ ( n ) = . k Answer: ( 1 , 1 ) . 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 that 2 e e n 1 k k ≥ 2 . We now claim that 2 > . Write n = p · · · p , where the p are distinct primes and i 1 σ ( n ) φ ( n ) k e ≥ 1 for all i, and let q < q < · · · be the primes in ascending order. Then i 1 2 k k 2 e 2 e 2 i i ∏ ∏ n p p i i = = e +1 2 e e − 1 i i i p − 1 σ ( n ) φ ( n ) e − 1 i p − p i i i · ( p − 1) p i =1 i =1 i i p − 1 i k k ∞ ∏ ∏ ∏ 1 1 1 = ≤ < − 1 − e − 2 − 2 i 1 − p 1 − p 1 − q i i i i =1 i =1 i =1   ∞ ∞ ∞ ∏ ∑ ∑ 1 1   = = 2 j 2 n q i i =1 j =0 n =1 (( ) ( ) ( ) ) ∞ ∑ 1 1 1 1 1 1 1 1 7 < 1 + = 1 + − + − + − + · · · = < 2 . 2 n − 1 2 1 3 2 4 3 5 4 n =2 2 n It follows that there can be no solutions to k = other than n = k = 1 . σ ( n ) φ ( n ) Grab Bag - Miscellaneous Problems [ 130 ] 4