We call a divisor $d$ of a positive integer $n$ special if $d + 1$ is also a divisor of $n$. Prove: at most half the positive divisors of a positive integer can be special. Determine all positive integers for which exactly half the positive divisors are special.
Problem
Source:
Tags: number theory
08.08.2015 17:37
If a divisor $d$ of $n$ is at least $\sqrt{n}$, it cannot be special: Because of $\textnormal{gcd}(d,d+1)=1$, this would imply $d(d+1) \mid n$, but $d(d+1) > d^2 \geq n$. Since at most half of the divisors of $n$ are less then $\sqrt{n}$ (because for each of them, $\frac{n}{d}$ also divides $n$ and is greater than $\sqrt{n}$), the result follows. If exactly half of the positive divisors of $n$ are special, $n$ cannot be a square because $\sqrt{n}$ canĀ“t be a divisor then. Then for each divisor $d$ of $n$ with $d < \sqrt{n}$, we must have $d+1 \mid n$. Because of $1 \mid n$, every positive integer $k \leq \lceil \sqrt{n} \rceil$ divides $n$. In particular, $n$ is even. If $n \geq 5$, then it must also be divisble by $3$, and if $n \geq 17$, also by $5$. From this we get that for $n \leq 25$, exactly $2, 6, 12$ work. Now let $n > 25$ and $r = \lfloor \sqrt{n} \rfloor > \sqrt{n}-1$. Then $r-1,r,r+1$ divide $n$, and the greatest common divisor of two of them is $2$. Hence $$\frac{(r-1)r(r+1)}{2} \mid n \Longrightarrow (r-1)r(r+1) \leq 2n \Longrightarrow \sqrt{n}(\sqrt{n}-1)(\sqrt{n}-2) < 2n \Longrightarrow n+2 < 5\sqrt{n}.$$ It is easy to see that this cannot be true for $n > 25$. Hence, all possibilities are $2$, $6$ and $12$.