Number theoryDifficulty 7.2National Olympiad, round 2Prove itSlovenia
For a positive integer n≥2 let τ(n) denote the number of positive divisors of n, and let σ(n) be the sum of these divisors. Prove that 2n+1≥τ(n)σ(n)≥223n. For each of these inequalities also determine when the equality holds.
Solution
First consider the right inequality. Let n=p1k1p2k2⋯psks, (where p1,…,ps are distinct primes and k1,…,ks are positive integers). Then τ(n)=(k1+1)(k2+1)⋯(ks+1) σ(n)=(1+p1+⋯+p1k1)(1+p2+⋯+p2k2)⋯(1+ps+⋯+psks)=σ(p1k1⋯psks). So τ(n)nσ(n)=(k1+1)p12k11+p1+⋯+p1k1⋅(k2+1)p22k21+p2+⋯+p2k2⋯(ks+1)ps2ks1+ps+⋯+psks. The factors in this product are independent, so it suffices to show that each one is bounded from below by 223. We would like to prove that (k+1)p2k1+p+⋯+pk≥223 for all p≥2 and k≥1 (the left-hand side is the smallest when p=2,k=1). Let x=p. For every positive integer k the function fk(x)=xk1+x2+x4+⋯+x2k is increasing when x>1. When k=1 and x>y>1 we have f1(x)−f1(y)=(x−y)+xyy−x=(x−y)(1−xy1)>0. In general f2l(x)=1+f1(x2)+⋯+f1(x2l),(8) f2l+1(x)=f1(x3)+⋯+f1(x2l+1).(9) The functions f2l(x) and f2l+1(x) are obviously increasing. So, fk(x) is increasing in x. ⇒p2k1+p+p2+⋯+pk⇒(k+1)p2k1+p+p2+⋯+pk≥22k1+2+⋯+2k≥(k+1)22k1+2+⋯+2k Define g(k)=(k+1)22k1+2+⋯+2k, k∈N. Let us show that g(k) is increasing. g(k+1)−g(k)=(k+2)22k21+2(1+2+⋯+2k)−(k+1)22k1+2+⋯+2k=(k+1)(k+2)22k2(k+1)+(1+2+⋯+2k)(2k+2−2k−22)>0 So, (k+1)p2k1+p+p2+⋯+pk≥(k+1)22k1+2+⋯+2k≥223 We conclude that τ(n)nσ(n)≥(223)s≥223 The equality holds when n=2.
Finally, consider the left inequality. Denote by 1=d1<d2<⋯<dτ(n)=n all divisors of n. Then σ(n)=∑i=1τ(n)di. Since d1n,d2n,…,dτ(n)n are precisely the divisors of n, we also have σ(n)=∑i=1τ(n)din.
For each divisor di we also have di+din≤n+1⟺di2−di(n+1)+n≤0⟺(n−di)(1−di)≤0,(10) and the equality holds if and only if either di=1 or di=n. Now, we can estimate τ(n)σ(n)=2τ(n)σ(n)+σ(n)=2τ(n)∑i=1τ(n)di+∑i=1τ(n)din=2τ(n)∑i=1τ(n)(di+din)≤≤2τ(n)∑i=1τ(n)(n+1)=2τ(n)τ(n)⋅(n+1)=2n+1. The equality holds if and only if it holds for each (10). This is only the case when τ(n)≤2. So, the equality holds when either n=1 or n is a prime.
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 reproduced verbatim; metadata (topic, difficulty) added by this project.