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

modular arithmeticnumber theoryprimitive-roots

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.

A solution to the problem above

Best Answer

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

Related Question