This question is linked to my previous question, but I wanted a clearer explanation.
Suppose we have a huge number of that type with a huge $k$.
$$\sum_{a=1}^N a^{k} =1^{k}+2^{k}+3^{k}+...+N^{k},$$
and we want to find the smallest prime factor. We want to find the smallest $p$ for which
$$\sum_{a=1}^N a^{k} =1^{k}+2^{k}+3^{k}+...+N^{k}\equiv 0 \pmod p.$$
Let's review some facts about $a^{k}\pmod p$: by Fermat's Little Theorem $a^{k}\equiv 1\pmod p$ if $(p-1)\mid k∧p∤a$. Otherwise $a^{k}≢1\pmod p$ and in the particular case when $p|a⟹a^{k} \equiv 0\pmod p$. If the exponent is a multiple of $p-1$, the powers becomes equal to 1.
Okay, now it's here where I get stuck. How do I continue to find the smallest prime factor? Should I count each $a^{k} \pmod p$? I think that I am missing something but I can't nail it.