Find the smallest prime divisor of $1^{60}+2^{60}+...+33^{60}$ 
Find the smallest prime divisor of $1^{60}+2^{60}+...+33^{60}$.

I found a solution online, but I have a few questions:


*

*In the beginning, the solver claims that $S^n = \begin{cases}S &\text{if } (p-1)\nmid n,\\ \{1\}&\text{if } (p-1)\mid n\end{cases}$. Can he do this because $S^n \equiv S\mod n \text{ if } (p-1)\nmid n$ and $S^n\equiv 1\mod n \text{ if } (p-1)\mid n$? $n$ does not need to be prime, so how does this follow from Fermat's Little Theorem? Apparently this claim is wrong.

*I don't get why $\sum_{n}$ is divisible by $n$ if $(p-1)\nmid n$ and equivalent to $-1\mod n$ otherwise. I guess I can sort of understand why it could be a multiple of $n$, but why does that depend on whether $(p-1)\mid n$?

*Why was the solver able to claim that $T_{k,n}=q\sum_{n}+1^n+2^n+\dots+r^n=\begin{cases}1^n+2^n+\dots+r^n &\text{ if } (p-1)\nmid n\\ r-q &\text { if } (p-1)\mid n\end{cases}$? The first case I understand because if $(p-1)\nmid n$, then $\sum_{n}\equiv 0\mod n$. And as for the second case, I know he uses the fact that if $(p-1)\mid n,\text { then } \sum_{n}\equiv -1\mod n$.


Everything else I understand.



 A: 1) The claim that the set $S^n$ is either $S$ or $\{1\}$ is false.  Take $p = 7$, $S = \{1,2,3,4,5,6\}$ (each element is the least positive representative in their residue classes modulo $p$), and $n = 2$.  According to the claim, since $6 \not\mid 2$, $S^2 = S$.  We compute $$  S^2 = \{1,4,2,2,4,1\} = \{1,2,4\} \neq S  \text{.}  $$  The argument that the powers permute the elements of $S$ could only be true if every nonzero residue modulo $p$ were a primitive root modulo $p$, which is wildly false.
2) This has some hope of being true.  I'd start with Faulhaber's formula and see where that took me.
3) Notice that $T_{k,n}$ is a sum of powers of residues modulo $p$, so the first $p-1$ terms are a copy of $\Sigma_n$, the next term is a power of a representative from the zero residue class, and then we start over.  This means each block of $p$ terms is $\Sigma_n + 0$.  By the division algorithm, there are $q$ blocks followed by $r$ remaining residue powers (starting with a representative of the residue class containing $1$).
A: Note that the solution is much more complicated than it needs.
First note that for $p \in \{ 2, 3, 5, 7, 11, 13 \}$ since $p-1|60$ you have
$$x^{60} = \left\{
\begin{array}{lc}
1 & \mbox{ if  } p \nmid x \\
0 & \mbox{ if  } p \mid x \\
\end{array}
\right.$$
Using this, it is easy to show that no prime in the set $ \{ 2, 3, 5, 7, 11, 13 \}$ divides your sum.
Next, for $p=17$, let 
$$S=1^{60}+2^{60}+…+33^{60}$$
Note that for each $a \in \{ 1, 2, 3,.., 16 \} \pmod{17}$ the function $x \to ax$ is a permutation of the numbers $1,2,3,...,33 \pmod{17}$. 
From here it is easy to deduce that 
$$S=a^{60}S \pmod{17}$$
If you can find an $a \neq 0$ such that $a^{60} \neq 1 \pmod{17}$ (which you can argue theoretically that it exists via primitive roots, but you can find very fast by test and error) you can deduce from here that $S \equiv 0 \pmod{17}$.
P.S. Note here that $gcd(60, 17-1)=4$. Aince $a^{16}=1 \pmod{17}$ for all $ \neq 0$, you get immediately that $$a^{60} \equiv 1 \pmod{17} \Leftrightarrow a^{4} \equiv 1 \pmod{17} \Leftrightarrow  (a^2-1)(a^2+1) \equiv 0 \pmod{17}\\ \Leftrightarrow  (a^2-1)(a^2-16) \equiv 0 \pmod{17}\\ \Leftrightarrow  (a-1)(a+1)(a-4)(a+4) \equiv 0 \pmod{17}$$
