Number theoryDifficulty 5.9AIME, harderProve itRomania
For each positive integer x let σ(x) be the sum of its positive divisors and τ(x) be the number of the positive divisors of x. Find all positive integers n such that σ(τ(n))=n.
Solution
Let τ(n)=k and let d be a divisor of n, such that d≤n. Since dn also divides n and dn≥n, we infer that τ(n)≤2n, for any n∈N∖{0}, (1).
Also, if 1=d1<d2<⋯<dk=n are the divisors of n, then 2σ(n)=(d1+dk)+(d2+dk−1)+⋯+(dk+d1)=(d1+d1n)+⋯+(dk+dkn). But, if d divides n, then 1+n−d−dn=dn(d−1)−(d−1)=d(n−d)(d−1)≥0. Consequently, σ(n)≤21τ(n)⋅(n+1), (2).
We infer that n=σ(τ(n))≤21τ(τ(n))⋅(τ(n)+1)≤21⋅2τ(n)⋅(2n+1)≤2n⋅(2n+1).
Successively, this leads to n2≤2n(4n+4n+1)⇔nn≤2(4n+4n+1)⇔n≤8+n8+n2. Suppose, by contradiction, that n≥81. Then n≥9 and 8+98+812<9≤n, which is a contradiction. Hence, n≤80, which means that n can only have one of the following forms: 1,p,p2,p3,p4,p5,pq,p2q,p3q,p4q,p2q2,p3q2,pqr,p2qr, where p,q,r are prime numbers.
Every such possible n has at most 12 divisors. Studying all cases for τ(n)∈{1,2,…,12}, we easily find that the only solutions are n=1,n=3,n=4 and n=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.