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: .
We have shown that can be written s.t it's a product of fractions of the form
can be written in such a way too.
Hence we have shown that all odds less than satisfies
is true. Since we have shown P(1) is true, it must hence be true for all odd integers.
Therefore, is odd. ∎