Largest integer such that $n+5$ divides $n^3+89$ 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! 
 A: 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.
A: Synthetic division.
$n^3 + 89 = n^3 + 5n^2 - 5n^2 + 89=$
$(n+5)n^2 - 5n^2 + 89=$
$(n+5)n^2 - 5n^2 - 25n + 25n +89=$
$(n+5)n^2 - (n+5)5n + 25n + 89 =$
$(n+5)n^2 - (n+5)5n + 25n + 125 -125+89=$
$(n+5)n^2 - (n+5)5n + (n+5)25 - 36=$
$(n+5)(n^2-5n + 25) -36$.
So if $n+5$ divides that, then we must have $n+5| 36$
If $n=31$ then $31+5 = 36$ and division is possible, but if $n > 31$ then $n+5>36$ and division is impossible.
....
Alternatively $n^3 + 89 \equiv 0 \pmod {n+5}$ so
$(-5)^3 + 89= -36 \equiv 0\pmod {n+5}$ 
So $n+5|36$
