Let $\sigma (n)$ shows the number of positive divisors of $n$. Let $s(n)$ be the number of positive divisors of $n+1$ such that for every divisor $a$, $a-1$ is also a divisor of $n$. Find the maximum value of $2s(n)- \sigma (n) $.
Problem
Source: Turkey EGMO TST 2019 #4
Tags: number theory, number theory proposed
16.07.2020 12:05
Do you mean $2s(n)-\sigma(n)$?
04.04.2021 21:37
Let's bump this. Solution?
04.04.2021 22:01
I claim the answer is two. That is, $2s(n)-\sigma(n)\le 2$ with equality achieved, e.g., for $n=3$. Call a $d\mid n$ to be good if $d+1\mid n+1$. Let $d\notin\{1,n\}$ be a good divisor of $n$, set $n=dk$. I claim $k$ cannot be a good divisor: assume the contrary. We have on the one hand $d+1\mid n+1=dk+1$ and since $d\equiv -1\pmod{d+1}$, we have $d+1\mid k-1$. Likewise, we find $k+1\mid d-1$. Since $d,k>1$, a contradiction is reached. Now, pair each $\sigma(n)-2$ divisors of $n$ into groups $(d,n/d)$. From the construction above each pair contributes to $s(n)$ at most once, yielding $s(n)\le \frac{\sigma(n)-2}{2} + 2$, that is $2s(n)-\sigma(n)\le 2$. Since the equality is attained for $n=3$, we complete the proof. Remark. It is not hard to see that the equality actually holds infinitely often, e.g. for any prime $p>2$.