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.