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

英文解析

30. [ 20 ] How many positive integers k are there such thatk
    ( 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 ) = ( h a, h b ) where gcd( A, B ) = 1.
    k 2013 AB
    Making these subtitutions yields ( h a + h b ) = h aB , so k = . Because A and B are relatively
    2013 A + Bprime, 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 alsodistinct for some relatively prime non-ordered pair ( A, B ). Let n = A + B = C + D . Assume
    2013 AB 2013 CDthat = , or equivalently, A ( n − A ) = C ( n − C ). After some rearrangement, we haven 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 =
    1006.2
    Remark: It can be proven that the sum of the totients of all the factors of any positive integer Nequals N , but in this case, the sum of the totients can be computed by hand.