HMMT 二月 2013 · 冲刺赛 · 第 30 题

30. [ 20 ] How many positive integers k are there such that k ( a + b ) = lcm ( a, b ) 2013 has a solution in positive integers ( a, b )? Answer: 1006 First, we can let h = gcd( a, b ) so that ( a, b ) = ( hA, hB ) where gcd( A, B ) = 1. k 2013 AB Making these subtitutions yields ( hA + hB ) = hAB , so k = . Because A and B are relatively 2013 A + B prime, A + B shares no common factors with neither A nor B , so in order to have k be an integer, A + B must divide 2013, and since A and B are positive, A + B > 1. We first show that for different possible values of A + B , the values of k generated are distinct. In ′ ′ 2013 AB 2013 A B ′ ′ particular, we need to show that 6 = whenever A + B 6 = A + B . Assume that such an ′ ′ A + B A + B ′ ′ ′ ′ equality exists, and cross-multiplying yields AB ( A + B ) = A B ( A + B ). Since AB is relatively prime ′ ′ ′ ′ to A + B , we must have A + B divide A + B . With a similar argument, we can show that A + B ′ ′ must divide A + B , so A + B = A + B . Now, we need to show that for the same denominator A + B , the values of k generated are also distinct for some relatively prime non-ordered pair ( A, B ). Let n = A + B = C + D . Assume 2013 AB 2013 CD that = , or equivalently, A ( n − A ) = C ( n − C ). After some rearrangement, we have n n ( C + A )( C − A ) = n ( C − A ) This implies that either C = A or C = n − A = B . But in either case, ( C, D ) is some permutation of ( A, B ). Our answer can therefore be obtained by summing up the totients of the factors of 2013 (excluding 1) 2013 − 1 and dividing by 2 since ( A, B ) and ( B, A ) correspond to the same k value, so our answer is = 2

Remark: It can be proven that the sum of the totients of all the factors of any positive integer N equals N , but in this case, the sum of the totients can be computed by hand.