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

Question

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

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

1. 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.
2. 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$?
3. 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.

Answer 1

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}$$

Answer 2

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$).