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$.

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