Recognize that for contest questions like this, you generally have to do trial and error, so you might as well get started with that.
- Even if you have some magical way of showing that some particular prime $ p > 1000$ divides $n$, you'd still need to check all smaller primes just in case they might divide $n$. As such, you can't easily get away from trial and error.
- In addition, because you can't easily get away from trial and error, one would expect that the answer is one of the first few values that we try (in order for the question to be answerable within a reasonable time). I would be very surprised if you have to check 10 or more values.
(First bullet: Finding that particular prime)
In this case, we can let $ M = 2^2 \times 23^4$ and observe that $ M + 1 \mid M^5 + 1 = n$.
Then, since $M+1 = 5 \times 13 \times 17 \times 1013$, we conclude that $1013 \mid n$.
(Second bullet: Justifying that is truly the smallest)
However, we still do not know if $1009 \mid n$ as it might have divided the other factor.
So we'd still have to verify that $ 1009 \not \mid n$
Use FLT to conclude that $ 2^{1010} \times 23^{2020} \equiv 2^2 \times 23^4 \equiv 383 \not \equiv -1 \pmod{1009}$.
in order to conclude that 1013 is the smallest such prime.
Note: In my comment on river's solution, I suggest that FLT isn't that helpful in determining $p$. What I meant is that even if we know that $ 2^{p-1} \equiv 1 \pmod{p}$, all that we have is
$$2^{p -1011} \times 23^{ 2p - 2021} \equiv -1 \mod{p}$$
and will still need to check for various values of $p$.
FLT does help in that it makes $p-1011$ a lot smaller for $ p > 1000$, so the case checking is a lot easier.
However, we'd still have to check each $p$ (as per above), as opposed to almost immediately solving for $p$.
