Maths Olympiad Prep

Library / /4 of 16

, 2019

Number theory Difficulty 7.9 National olympiad, round 2 Prove it Turkey

For every positive integer nn, let σ(n)\sigma(n) denote the number of positive divisors of nn and let s(n)s(n) denote the number of positive divisors dd of nn such that d+1n+1d+1|n+1. Find the maximum value of
2s(n)σ(n). 2s(n) - \sigma(n).

Solution

Answer: 2.
It is easy to verify that for any odd prime number pp we have s(p)=σ(p)=2s(p) = \sigma(p) = 2 and hence 2s(n)σ(n)=22s(n) - \sigma(n) = 2. We will show that 2s(n)σ(n)22s(n) - \sigma(n) \le 2 for every positive integer nn. Let 1=d1<d2<<dk=n1 = d_1 < d_2 < \dots < d_k = n be positive divisors of nn. It is well known that didk+1i=nd_i d_{k+1-i} = n for 1ik1 \le i \le k. If di+1n+1d_i + 1|n+1, then di+1didk+1i+1(di+1)=di(dk+1i1)d_i + 1|d_i d_{k+1-i} + 1 - (d_i + 1) = d_i(d_{k+1-i} - 1). didk+1i1\Rightarrow d_i|d_{k+1-i} - 1 since (di+1,di)=1(d_i + 1, d_i) = 1. i=k\Rightarrow i = k or i<k+1ii < k+1-i. i=k\Rightarrow i = k or ikii \le k-i. s(n)1+k22s(n)k+2\Rightarrow s(n) \le 1 + \frac{k}{2} \Rightarrow 2s(n) \le 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.