IMO 1998/A3 solution

IMO 1998

Problem A3

For any positive integer n, let d(n) denote the number of positive divisors of n (including 1 and n). Determine all positive integers k such that d(n²) = k d(n) for some n.

Solution

Let n = p₁^a₁...p_r^a_r. Then d(n) = (a₁ + 1)(a₂ + 1) ... (a_r + 1), and d(n²) = (2a₁ + 1)(2a₂ + 1) ... (2a_r + 1). So the a_i must be chosen so that (2a₁ + 1)(2a₂ + 1) ... (2a_r + 1) = k (a₁ + 1)(a₂ + 1) ... (a_r + 1). Since all (2a_i + 1) are odd, this clearly implies that k must be odd. We show that conversely, given any odd k, we can find a_i.

We use a form of induction on k. First, it is true for k = 1 (take n = 1). Second, we show that if it is true for k, then it is true for 2^mk - 1. That is sufficient, since any odd number has the form 2^mk - 1 for some smaller odd number k. Take a_i = 2ⁱ((2^m - 1)k - 1) for i = 0, 1, ... , m-1. Then 2a_i + 1 = 2ⁱ⁺¹(2^m - 1)k - (2ⁱ⁺¹ - 1) and a_i + 1 = 2ⁱ(2^m - 1)k - (2ⁱ - 1). So the product of the (2a_i + 1)'s divided by the product of the (a_i + 1)'s is 2^m(2^m - 1)k - (2^m - 1) divided by (2^m - 1)k, or (2^mk - 1)/k. Thus if we take these a_is together with those giving k, we get 2^mk - 1, which completes the induction.

39th IMO 1998