I received a calendar with daily math problems as a Christmas gift, and so far most of the problems have been fun and challenging but not too difficult. However, I am completely stumped on the one for today, January 31. The problem reads:
What is the largest positive integer $n$ such that $n^3+89$ is divisible by $n+5$?
I struggled with it for a bit and found a few $n$'s which worked before throwing it at a computer. I tested up to $n=200,000$ and the only ones that satisfy the above condition are $\{ 1,4,7,13,31\}$. I then tried to prove that it doesn't work for $n\geq 31$ with induction for a bit before coming here. The calendar usually has the day of the month as the answer, so the answer should be 31, but I wasn't able to prove this.
Also, for all $n\geq 31$, at least up to $200,000$, the remainder on division of $n^3+89$ by $n+5$ is always $n-31$, if that is useful. Thanks for any help or tips!
Let $d = n + 5$. Then, $n \equiv -5 \pmod d$, plus $n + 5 \mid n^3 + 89$ means
$$\begin{equation}\begin{aligned} n^3 + 89 & \equiv 0 \pmod d \\ (-5)^3 + 89 & \equiv 0 \pmod d \\ -36 & \equiv 0 \pmod d \end{aligned}\end{equation}\tag{1}\label{eq1A}$$
This shows the maximum size of $d$ is $36$, so $n = 31$ is the largest positive integer.
Your observation about the remainder being $n - 31$ for $n \ge 31$ (note since $n^3 + 89 = (n^2 - 5n + 24)(n + 5) + n - 31$, it's actually always true, but this remainder is negative for $n \lt 31$) indicates this as well. This is because for $n \gt 31$, you have $0 \lt n - 31 \lt n + 5$, so there's a non-zero remainder when divided by $n + 5$ and, thus, $n + 5$ can't divide into it evenly.