1998 IMO Problems/Problem 3
Problem
For any positive integer , let
denote the number of positive divisors
of
(including 1 and
itself). Determine all positive integers
such that
for some
.
Solution
First we must determine general values for d(n):
Let , if
is an arbitrary divisor of
then
must have the same prime factors of
, each with an exponent
being:
.
Hence there are
choices for each exponent of Pi in the number d => there are
such d
where
are exponents of the prime numbers in the prime factorisation of
.
So we want to find all integers that can be represented by the product of fractions of the form
Obviously
is odd as the numerator is always odd.
It's possible for 1 (1/1) and 3
, which suggests that it may be possible for all odd integers, which we can show by induction.
: It's possible to represent
as the product of fractions
Base case:
Now assume that for
it's possible for all odds <
.
Since is odd,
where
is odd and
<
Let there be a number s.t
Also consider . ISTS
can be represented by a product of fractions of the form
in order to show
can be represented by product of fractions
, since
can be represented in such a manner too.
Using our definition of in terms of
:
And that is simply the product of fractions: ${2x+1}/{x+1} * {4x+1}/{2x+1} * .. * {2^zx+1}/{2^{z-1}x}.
We have shown that$ (Error compiling LaTeX. Unknown error_msg)k/y{2n+!}/{n+1}\implies k$can be written in such a way too.
Hence we have shown that all odds less than$ (Error compiling LaTeX. Unknown error_msg)kP(n)\implies P(k)$is true. Since we have shown P(1) is true, it must hence be true for all odd integers.
Therefore,$ (Error compiling LaTeX. Unknown error_msg)d(n^2)/d(n) = k\iff k$ is odd. ∎