CroatianCompetitions

One such number is $a = -95^4$.
For that $a$ we have $P(95) = P(0) = 0$, so $n$ divides $P(95) - P(0)$ for every positive integer $n$, and $n$ does not divide $95 - 0$ if $n$ is not a divisor of $95$. Therefore the statement is valid for only finitely many positive integers $n$.

Let us show that the statement is valid for $n = 95$. Let $k, l \in \mathbb{Z}$ such that $95 \mid P(k) - P(l)$. Since $95 \mid a$ we conclude that $95 \mid k^5 - l^5$. We want to show that $95 \mid k - l$, so it is sufficient to prove that $5 \mid k - l$ and $19 \mid k - l$.

By Fermat's little theorem we have $k^5 \equiv k \pmod{5}$ and $l^5 \equiv l \pmod{5}$, so it follows that $5 \mid k - l$ because $5 \mid k^5 - l^5$.

Also by Fermat's little theorem, if $k$ and $19$ are relatively prime then $k^{18} \equiv 1 \pmod{19}$, so $k^{54} = (k^{18})^3 \equiv 1 \pmod{19}$. Therefore $k^{55} \equiv k \pmod{19}$ whether $k$ is divisible by $19$ or not. Analogously $l^{55} \equiv l \pmod{19}$. We conclude that $k \equiv (k^5)^{11} \equiv (l^5)^{11} \equiv l \pmod{19}$, i.e. $19 \mid k - l$, which is what we had to prove.