# 2004 IMO Shortlist Problems/N1

## 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.*