Maths Olympiad Prep

Library / /58 of 82

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 Di2D_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. 3d(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+s4=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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.