Tessellate S.T.E.M.S. (2019) - Mathematics - Category A (School) - Set 3 - Objective Problem 2

For odd primes $p,$ first throw out the $p$ values in the sum with $p|n$ , as the fractional part will be zero. Now there are $p(p-1)$ values of $n$ in the sum not divisible by $p.$ These pair off: it's not hard to see via the binomial theorem that $n^p + (p^2-n)^p$ is divisible by $p^2,$ so $\frac{n^p}{p^2} + \frac{(p^2-n)^p}{p^2}$ is an integer, so the corresponding fractional parts must sum to $1.$ Hence the sum equals exactly $\frac{p(p-1)}2,$ and it's easy to find that $\fbox{67}$ is the smallest prime $p$ such that $\frac{p(p-1)}2 > 2016.$