2007 Indonesia MO Problems/Problem 2
Problem
For every positive integer , denote the number of positive divisors of and denote the sum of all positive divisors of . For example, and . Let be a positive integer greater than .
(a) Prove that there are infinitely many positive integers which satisfy .
(b) Prove that there are finitely many positive integers which satisfy .
Solution
For both parts, let , where is a prime number and is a nonnegative integer. For given value , we know that and .
Because the value of is only affected by the values of , one can change the value of and still have the same value of . Since there are an infinite number of primes, there would be an infinite values of that would equal a set value .
As for the value of , note that for positive integers where , we have . Thus, because whenever , if , then we must have , making .
Therefore, there are only a limited number of primes that can be a factor of , and for a prime that is a factor of , there is an upper bound of the value of . Because there are a limited number of possible values of and , there are only a finite values of where .
See Also
2007 Indonesia MO (Problems) | ||
Preceded by Problem 1 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 | Followed by Problem 3 |
All Indonesia MO Problems and Solutions |