Maths Olympiad Prep

Library / Croatian Mathematical Competitions /79 of 114

Croatian Mathematical Competitions

Number theory Difficulty 6.0 AIME, harder Prove it Croatia

For a positive integer nn denote by s(n)s(n) the sum of all positive divisors of nn and by d(n)d(n) the number of positive divisors of nn. Determine all positive integers nn such that
s(n)=n+d(n)+1. s(n) = n + d(n) + 1.
(Nikola Adžaga)

Solution

Observe that n=1n = 1 is not a solution, so d(n)≥2d(n) \ge 2.
It is impossible that d(n)=2d(n) = 2, since then nn would be prime and given equation would reduce to 1+n=n+2+11 + n = n + 2 + 1, so d(n)≥3d(n) \ge 3.
Let 1=D1<D2<⋯<Dd=n1 = D_1 < D_2 < \cdots < D_d = n be the divisors of nn. The given equation can then be written as
1+∑i=2d(n)−1Di+n=n+d(n)+1. 1 + \sum_{i=2}^{d(n)-1} D_i + n = n + d(n) + 1.
Since Di≥2D_i \ge 2 for all i∈{2,3,…,d(n)−1}i \in \{2, 3, \dots, d(n) - 1\}, we get d(n)=∑i=2d(n)−1Di≥(d(n)−2)⋅2d(n) = \sum_{i=2}^{d(n)-1} D_i \ge (d(n) - 2) \cdot 2,
hence d(n)≤4d(n) \le 4, i.e. 3≤d(n)≤43 \le d(n) \le 4.
For d(n)=3d(n) = 3, number nn is a square of some prime pp and given equation reduces to
1+p+p2=p2+3+1, 1 + p + p^2 = p^2 + 3 + 1,
hence p=3p = 3 and n=p2=9n = p^2 = 9.
For d(n)=4d(n) = 4, there are two possibilities:
a) If nn is product of some primes qq and rr (q<rq < r), then the given equation implies 1+q+r+qr=qr+4+11 + q + r + qr = qr + 4 + 1, thus q+r=4q + r = 4. There are no such primes qq and rr.
b) If nn is a cube of some prime ss, then the given equation means that 1+s+s2+s3=s3+4+11+s+s^2+s^3 = s^3 + 4 + 1, thus s2+s−4=0s^2 + s - 4 = 0. There is no such prime ss.

Therefore, the only solution is n=9n = 9.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.