1998 IMO Problems/Problem 3

Problem

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

Solution

First we must determine general values for d(n): Let , if d is an arbitrary divisor of n then d must have the same prime factors of n, each with an exponent being: . Hence there are choices for each exponent of Pi in the number d => there are such d

=> where Ai are exponents of the prime numbers in the prime factorisation of n.

=> $d(n^2)/d(n) = {(2A1 + 1)(2A2 + 1)..(2Ac + 1)}/{A1+1)..(Ac+1)}

So we want to find all integers k that can be represented by the product of fractions of the form$ (Error compiling LaTeX. Unknown error_msg)(2n+1)/(n+1)$Obviously k is odd as the numerator is always odd. It's possible for 1 (1/1) and 3 (5/3 * 9/5), which suggests that it may be possible for all odd integers, which we can show by induction.

P(k): It's possible to represent k as the product of fractions$ (Error compiling LaTeX. Unknown error_msg)(2n+1)/(n+1)k\geq 3$it's possible for all odds < k.

Since k is odd,$ (Error compiling LaTeX. Unknown error_msg)k+1 = 2^z * y$ where y is odd and y < k