Proving that $k|(n^k-n)$ for prime $k$

Question

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

Answer 1

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.

Answer 2

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.