Find all integers $k \ge 5$ for which there is a positive integer $n$ with exactly $k$ positive divisors $1 = d_1 <d_2 < ... <d_k = n$ and $d_2d_3 + d_3d_5 + d_5d_2 = n$.
Problem
Source: Estonia IMO TST 2018 p8
Tags: Divisors, number theory
08.02.2022 10:45
bummp bump
20.12.2022 00:21
Let $p$ be the smallest prime divisor of $n$. From the given equation, since $d_2 \mid n$, $d_3 \mid n$ and $d_5 \mid n$, it follows that $d_2 \mid d_3d_5$, $d_3 \mid d_2d_5$ and $d_5 \mid d_2d_3$. In particular, $d_2 = p \mid d_3d_5$. Case 1: $p \mid d_3$. Notice that $d_3 = pq$ for $q \neq p$ and $q$ prime immediately yields a contradiction. So, $d_3 = p^2$. Moreover, we have that $d_5 \mid d_2d_3 = p^3$, so $d_5 = p^3$. Thus, $n = d_2d_3+d_3d_5+d_5d_2 = p^3(p^2+p+1)$. Now since for any prime $p$ the inequality $p^2 < p^2+p+1 < p^3$ clearly holds and $p^2+p+1 \mid n$, $d_4$ must be $p^2+p+1$. We have found two divisors $d_4$ and $d_5$ such that $d_4d_5 = n$. From here, the list of divisors of $n$ (in ascending order) is $$ 1, p, p^2, p^2+p+1, p^3, p(p^2+p+1), p^2(p^2+p+1), p^3(p^2+p+1) $$It can be readily seen that $p^2+p+1$ must be prime and $n = p^3(p^2+p+1)$ with $p$ and $p^2+p+1$ prime satisfies the conditions. Case 2: $p \mid d_5$. Observe that we get a contradiction if $d_5$ and $d_2$ differ by at least three prime factors. If they differ by two prime factors, we again get a contradiction (just check manually the possible subcases). Since $p \mid d_5$, $d_5 = p^2$ or $d_5 = pq$ for some prime $q \neq p$. If $d_5 = p^2$, $d_3 \mid d_5d_2 = p^3$, so $d_3 = p$ or $d_3 = p^2$, contradiction. Therefore, $d_5 = pq$ for a prime $q \neq p$. Now, $d_3 \mid d_5d_2 = p^2q$ and $d_5 = pq \mid pd_3 = d_2d_3$, $q \mid d_3$ and $d_3 = q$. Then, $n = d_2d_3+d_2d_5+d_3d_5 = pq(p+q+1)$, so $d_4 = p+q+1$ unless $(p, q)$ is $(2, 3)$. Note, however, that for $(p, q) = (2, 3)$, $n = 36$ satisfies the condition. For all other prime pairs $(p, q)$, $p+q+1 < pq$. Therefore, as we did in Case 1, there are exactly eight divisors of n so $p+q+1$ must be prime. Hence, similar to the above case, $n = pq(p+q+1)$ with $p$, $q$ and $p+q+1$ prime satisfies the conditions. In conclusion, all numbers satisfying our condition are $n = 36$, $n = p^3(p^2+p+1)$ ($p$ and $p^2+p+1$ are prime) and $n = pq(p+q+1)$ ($p$, $q$ and $p+q+1$ are prime). Therefore, all possible values of $k$ are $8$, $9$.