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