<s>[INST] Prove that the number $1^k + 2^k + ... + 12^k$ is divisible by $13$ Prove that the number $1^k + 2^k + ... + 12^k$ is divisible by $13$ for $k = 1, 2, ..., 11$.
My attempt:
If k is odd number, then $1^k +...+6^k +7^k ... + 12^k \equiv 1^k + ... + 6^k - 6^k - 5^k - ... -1^k \equiv 0 (mod 13)$.
But if k is even number then $2(1^k + ... + 6^k)$
Please give a good hint or explain clearly how to solve. Thanks you
 [/INST] To be specific: $2$ is a primitive root modulo $13$. Hence any number from $1$ to $12$ can be written uniquely as $2^n$, for some $n$ between $1$ and $12$. Hence after a rearrangement   your sum becomes:
$$2^k+ 2^{2k}+ \dots + 2^{12k} \pmod{13}.$$
If we denote your sum by $S$, then
$$ S \equiv \sum\limits_{n=1}^{12} 2^{nk} \pmod {13}.$$
Notice that the right hand sum is nothing but
$$ 2^k (2^{12k}-1) = 2^k (2^{12}-1)r.$$
Where $r$ is some integer. $2^{12}-1$ is divisible by $13$. Hence $S$ should be divisible by $13$.
</s>