HMMT-Feb 2013 guts, Problem 30

How many positive integers $k$ are there such that \[ \frac{k}{2013}(a+b)=l c m(a, b) \] has a solution in positive integers $(a, b)$ ?

Solution: First, we can let $h=\operatorname{gcd}(a, b)$ so that $(a, b)=(h A, h B)$ where $\operatorname{gcd}(A, B)=1$. Making these subtitutions yields $\frac{k}{2013}(h A+h B)=h A B$, so $k=\frac{2013 A B}{A+B}$. Because $A$ and $B$ are relatively 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 particular, we need to show that $\frac{2013 A B}{A+B} \neq \frac{2013 A^{\prime} B^{\prime}}{A^{\prime}+B^{\prime}}$ whenever $A+B \neq A^{\prime}+B^{\prime}$. Assume that such an equality exists, and cross-multiplying yields $A B\left(A^{\prime}+B^{\prime}\right)=A^{\prime} B^{\prime}(A+B)$. Since $A B$ is relatively prime to $A+B$, we must have $A+B$ divide $A^{\prime}+B^{\prime}$. With a similar argument, we can show that $A^{\prime}+B^{\prime}$ must divide $A+B$, so $A+B=A^{\prime}+B^{\prime}$. 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 that $\frac{2013 A B}{n}=\frac{2013 C D}{n}$, or equivalently, $A(n-A)=C(n-C)$. After some rearrangement, we have $(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) and dividing by 2 since $(A, B)$ and $(B, A)$ correspond to the same $k$ value, so our answer is $\frac{2013-1}{2}=$ 1006 . 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. $\fbox{1006}$.

Answer: 1006