Number theoryDifficulty 7.9National olympiad, round 2Prove itTurkey
For every positive integer n, let σ(n) denote the number of positive divisors of n and let s(n) denote the number of positive divisors d of n such that d+1∣n+1. Find the maximum value of 2s(n)−σ(n).
Solution
Answer: 2. It is easy to verify that for any odd prime number p we have s(p)=σ(p)=2 and hence 2s(n)−σ(n)=2. We will show that 2s(n)−σ(n)≤2 for every positive integer n. Let 1=d1<d2<⋯<dk=n be positive divisors of n. It is well known that didk+1−i=n for 1≤i≤k. If di+1∣n+1, then di+1∣didk+1−i+1−(di+1)=di(dk+1−i−1). ⇒di∣dk+1−i−1 since (di+1,di)=1. ⇒i=k or i<k+1−i. ⇒i=k or i≤k−i. ⇒s(n)≤1+2k⇒2s(n)≤k+2 and the result follows.
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.