2007 Indonesia MO Problems/Problem 2

Problem

For every positive integer $n$ , $b(n)$ denote the number of positive divisors of $n$ and $p(n)$ denote the sum of all positive divisors of $n$ . For example, $b(14)=4$ and $p(14)=24$ . Let $k$ be a positive integer greater than $1$ .

(a) Prove that there are infinitely many positive integers $n$ which satisfy $b(n)=k^2-k+1$ .

(b) Prove that there are finitely many positive integers $n$ which satisfy $p(n)=k^2-k+1$ .

Solution

For both parts, let $n = \prod_{i=1}^\infty {p_i}^{q_i}$ , where $p_i$ is a prime number and $q_i$ is a nonnegative integer. For given value $n$ , we know that $b(n) = \prod_{i=1}^\infty (q_i + 1)$ and $p(n) = \prod_{i=1}^\infty (\sum_{j=0}^{q_i} p_i^j)$ .

Because the value of $b(n)$ is only affected by the values of $q_i$ , one can change the value of $p_i$ and still have the same value of $b(n)$ . Since there are an infinite number of primes, there would be an infinite values of $n$ that would equal a set value $b(n)$ .

As for the value of $p(n)$ , note that for positive integers $a, b$ where $a > b$ , we have $\sum_{j=0}^{a} p_i^j > \sum_{j=0}^{b} p_i^j$ . Thus, because $\sum_{j=0}^{q_i} p_i^j > p_i$ whenever $q_i \ge 1$ , if $p_i > k^2 - k + 1$ , then we must have $q_i = 0$ , making ${p_i}^{q_i} = 0$ .

Therefore, there are only a limited number of primes $p_i$ that can be a factor of $n$ , and for a prime $p_i$ that is a factor of $n$ , there is an upper bound of the value of $q_i$ . Because there are a limited number of possible values of $p_i > 1$ and $q_i$ , there are only a finite values of $n$ where $p(n) = k^2 - k + 1$ .

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

Page

Toolbox

Search

2007 Indonesia MO Problems/Problem 2

Problem

Solution

See Also