Hong Kong Preliminary Selection Contest

Let $p$ be any prime factor of $n+1$. Then $p$ is a prime factor of $(n+1)(2n+15)$ and hence of $n(n+5)$ as well. Since $n(n+5)=(n+1)(n+4)-4$, we conclude that $p$ divides $4$, and so $p$ can only be $2$. In the same way, we find that the only possible prime divisors of $n+5$ are $2$ and $5$.

Let $n+1=2^a$ and $n+5=2^b{5}^c$. Then we have $2^a+4=2^b{5}^c$. Note that if $a\ge 5$, the left-hand side is a multiple of $4$ but not a multiple of $8$. Hence we must have $b=2$ and the equation becomes $2^{a-2}+1=5^c$. As $a\ge 5$, this gives $5^c\equiv 1(\mathrm{mod}8)$, forcing $c$ to be even. However, if $c$ is even, then $2^{a-2}=5^c-1\equiv (-1{)}^c-1=0(\mathrm{mod}3)$, which is impossible.

This means that $a$ can only be $0,1,2,3$ or $4$. To find the greatest possible value of $n$, it suffices to show that $a=4$ is possible. Indeed, if $a=4$, then $n=15$, and we have $(n+1)(2n+15)=16\times 45=2^4\times 3^2\times 5$ and $n(n+5)=15\times 20=2^2\times 3\times 5^2$. Therefore, the answer is $15$.