Proving that $k|(n^k-n)$ for prime $k$ Prove that for any integer $n$,we have $(n^k)- n$ is divisible by $k$ for $k=3,5,7,11,13$
I tried using prime factorization but that does not work here
HINT: there are several ways to prove the congruence of the OP,  which corresponds to Fermat little theorem. A rather simple one: consider the sequence of integers $$n,2n,3n,…,(k−1)n$$
Among these integers, none is congruent modulo k to the others (this is not difficult to prove). So ${1,2,3,…,k−1}$ is the set of reduced residue system modulo k.
Taking the product, we have
$$n \cdot 2n \cdot 3n \cdot \dots \cdot (k-1)n \\ \equiv 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (k-1) \pmod k
$$
and then
$$n^{k-1} \cdot (k-1)! \equiv (k-1)! \pmod k$$
Now you can easily complete the proof.
Agreed, this is just Fermat's little theorem restated, i.e. $n^{k-1 }\equiv 1\pmod k$ where$ k$ is prime. So $n^k\equiv n\pmod k$ , which is what you are trying to show.