Maths Olympiad Prep

Library / /3 of 11

Number theory Difficulty 5.9 AIME, harder Prove it Romania

For each positive integer xx let σ(x)\sigma(x) be the sum of its positive divisors and τ(x)\tau(x) be the number of the positive divisors of xx.
Find all positive integers nn such that σ(τ(n))=n\sigma(\tau(n)) = n.

Solution

Let τ(n)=k\tau(n) = k and let dd be a divisor of nn, such that dnd \le \sqrt{n}. Since nd\frac{n}{d} also divides nn and ndn\frac{n}{d} \ge \sqrt{n}, we infer that τ(n)2n\tau(n) \le 2\sqrt{n}, for any nN{0}n \in \mathbb{N} \setminus \{0\}, (1).

Also, if 1=d1<d2<<dk=n1 = d_1 < d_2 < \dots < d_k = n are the divisors of nn, then
2σ(n)=(d1+dk)+(d2+dk1)++(dk+d1)=(d1+nd1)++(dk+ndk). 2\sigma(n) = (d_1 + d_k) + (d_2 + d_{k-1}) + \dots + (d_k + d_1) = \left(d_1 + \frac{n}{d_1}\right) + \dots + \left(d_k + \frac{n}{d_k}\right).
But, if dd divides nn, then 1+ndnd=n(d1)d(d1)=(nd)(d1)d01 + n - d - \frac{n}{d} = \frac{n(d-1)}{d} - (d-1) = \frac{(n-d)(d-1)}{d} \ge 0. Consequently, σ(n)12τ(n)(n+1)\sigma(n) \le \frac{1}{2}\tau(n) \cdot (n+1), (2).

We infer that n=σ(τ(n))12τ(τ(n))(τ(n)+1)122τ(n)(2n+1)2n(2n+1)n = \sigma(\tau(n)) \le \frac{1}{2}\tau(\tau(n)) \cdot (\tau(n)+1) \le \frac{1}{2} \cdot 2\sqrt{\tau(n)} \cdot (2\sqrt{n}+1) \le \sqrt{2\sqrt{n}} \cdot (2\sqrt{n}+1).

Successively, this leads to
n22n(4n+4n+1)nn2(4n+4n+1)n8+8n+2n. n^2 \le 2\sqrt{n}(4n + 4\sqrt{n} + 1) \Leftrightarrow n\sqrt{n} \le 2(4n + 4\sqrt{n} + 1) \Leftrightarrow \sqrt{n} \le 8 + \frac{8}{\sqrt{n}} + \frac{2}{n}.
Suppose, by contradiction, that n81n \ge 81. Then n9\sqrt{n} \ge 9 and 8+89+281<9n8 + \frac{8}{9} + \frac{2}{81} < 9 \le \sqrt{n}, which is a contradiction. Hence, n80n \le 80, which means that nn can only have one of the following forms: 1,p,p2,p3,p4,p5,pq,p2q,p3q,p4q,p2q2,p3q2,pqr,p2qr1, p, p^2, p^3, p^4, p^5, pq, p^2q, p^3q, p^4q, p^2q^2, p^3q^2, pqr, p^2qr, where p,q,rp, q, r are prime numbers.

Every such possible nn has at most 12 divisors. Studying all cases for τ(n){1,2,,12}\tau(n) \in \{1, 2, \dots, 12\}, we easily find that the only solutions are n=1,n=3,n=4n = 1, n = 3, n = 4 and n=12n = 12.

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.