2004 IMO Shortlist Problems/N1
Contents
[hide]Problem
(Belarus)
Let denote the number of positive divisors of the positive integer
. Prove that there exist infinitely many positive integers
such that the equation
does not have a positive solution .
This was also a problem on the 2005 TSTs for Australia and Germany.
Solutions
Solution 1
If , then
, i.e., there exists
such that
. The converse is also true, since
(i.e.,
.) Thus the existance of
such that
is equivalent to the existance of
such that
.
Note that for any integer has at most
divisors less than or equal to
, and for each divisor
, a divisor
. Hence we obtain the inequality
.
It is sufficient to prove that for prime , the equation
has no solutions. Assume the contrary. Clearly, if
is a solution, then
, so let
, where
is not divisible by
. We have
.
We must clearly have . If
, then
must be divisible by
, a contradiction, since
. On the other hand, if
, then by
we have
. This implies
, so
. But by
, we have
.
This implies , a contradiction for
.
Thus we must have . Here, we have
.
But by induction, we have , which implies
, a final contradiction.
Solution 2
As in the first solution, it is sufficient to show that there are infinitely many such that
has no solutions.
We note that for prime ,
is a non-decreasing function of
, for
. We also note that since there are only
positive integers less than or equal to
,
. We also note that
is a weak multiplicative function, so for relatively prime
,
.
Now, suppose that there exists some integer such that for all integers
,
. Let
be any prime greater than
. We claim that there is no integer
such that
. Suppose the contrary. Clearly, we must have
, so let
, for some
not divisible by
. If
is less than
, then the numerator of
is not divisible by
, a contradiction. If
, then we must have
, which implies
, a contradiction. So
. But then we have
,
a contradiction. Thus it is sufficient to prove the existance of one such that
has no solution
.
We will now prove that these is no integer such that
. Suppose that there is such an integer
. Since
and
for distinct primes
, it follows that
must be divisible by
, for some prime
. But then we have
,
a contadiction.
We will now prove that for no integer does the equation
hold. Suppose on the contrary that there exists such an
. We must have
, for some
not divisible by 5. We must clearly have
. In fact, we must have
, for
gives us
, which cannot be divisible by
. We cannot have
, either, since we then have
, which gives us
. Then
,
a contradiction. Thus does not exist and the problem is solved.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.