IMO 1998 SL 19

Origin: BLR

Problem

For any positive integer n, let \tau(n) denote the number of its positive divisors (including 1 and itself). Determine all positive integers m for which there exists a positive integer n such that \tau(n2) \tau(n) = m.

Solution

For n = p\alpha1 1 p\alpha2 2 \cdot \cdot \cdot p\alphar r , where pi are distinct primes and \alphai natural num- bers, we have \tau(n) = (\alpha1+1) \cdot \cdot \cdot (\alphar+1) and \tau(n2) = (2\alpha1+1) . . . (2\alphar+1). Putting ki = \alphai +1, the problem reduces to determining all natural values of m that can be represented as m = 2k1 −1 k1 \cdot 2k2 −1 k2 \cdot \cdot \cdot 2kr −1 kr . (1) Since the numerator \tau(n2) is odd, m must be odd too. We claim that every odd m has a representation of the form (1). The proof will be done by induction. This is clear for m = 1. Now for every m = 2k −1 with k odd the result follows easily, since m = 2k−1 k \cdot k, and k can be written as (1). We cannot do the same if k is even; however, in the case m = 4k −1 with k odd, we can write it as m = 12k−3 6k−1 \cdot 6k−1 3k \cdot k, and this works. In general, suppose that m = 2tk −1, with k odd. Following the same pattern, we can write m as m = 2t(2t −1)k −(2t −1) 2t−1(2t −1)k −(2t−1 −1) \cdot \cdot \cdot 4(2t −1)k −3 2(2t −1)k −1 \cdot 2(2t −1)k −1 (2t −1)k \cdot k. The induction is finished. Hence m can be represented as \tau(n2) \tau(n) if and only if it is odd.