Smallest prime divisor

Let $p$ be a prime. Let's review some facts of arithmetic modulo $p$ .

Let $n$ be an integer and consider the set $S = \{1, 2, \dots, p-1\}$ modulo $p$ . Define $S^n = \{1^n, 2^n, \dots, (p-1)^n\}$ . Then $S^n = \begin{cases} S & \text{if}\ (p-1) \not| n \\ \{1\} & \text{if}\ (p-1) | n \end{cases}$ Both statements follow from Fermat's Little Theorem. We see that taking powers of $S$ shuffles its elements around bijectively, but if the exponent is a multiple of $p-1$ , all powers of $S$ become equal to 1.

Next, I claim that $1 + 2 + \cdots + (p-1) \equiv 0\ \ \ \text{mod}\ p\ \ \ \text{for}\ p > 2.$ This is easily seen, because the elements can be paired: $1 + (p-1) = p \equiv 0$ , $2 + (p-2) = p \equiv 0$ , and so on. It follows nicely that for $p > 2$ , $\Sigma_n = 1^n + 2^n + \cdots + (p-1)^n \equiv \begin{cases} 0 & \text{if}\ (p-1)\not|n \\ -1 & \text{if}\ (p-1)|n\end{cases}.$ We can freely add the term $p^n$ , because $p \equiv 0$ anyway.

Next consider the sum $T_{k,n} = 1^n + 2^n + \cdots + k^n$ modulo $p$ . If $k = qp+r$ , then this sum is equal to $T_{k,n} = 1^n + 2^n + \cdots + k^n = q\Sigma_n + 1^n + 2^n + \cdots + r^n \equiv \begin{cases} 1^n + \cdots + r^n & \text{if}\ (p-1)\not|n \\ r-q & \text{if}\ (p-1)|n\end{cases}.$

Now we have the tools to solve this problem. We check the primes $p = 2, 3, 5, 7, \dotsc$ in order and calculate the sum $T = T_{33,60}$ modulo $p$ . The lowest prime $p$ for which it is zero is the answer.

• $p = 2$ . It is clear that 17 of the terms are odd, so that $T \equiv 1$ mod 2.

• $p = 3$ . Since $(3-1)|60$ and $33 = 11\cdot 3 + 0$ , $T \equiv 0 - 11 \equiv 1$ mod 3.

• $p = 5$ . We see $(5-1)|60$ , and $33 = 6\cdot 5 + 3$ , so that $T \equiv 3 - 6 \equiv 2$ mod 5.

• $p = 7$ . Again $(7-1)|60$ , and $33 = 4\cdot 7 + 5$ , so that $T \equiv 5 - 4 \equiv 1$ mod 7.

• $p = 11$ . Also $(11-1)|60$ , and $33 = 3\cdot 11 + 0$ , so that $T \equiv 0 - 3 \equiv 8$ mod 11.

• $p = 13$ . Once again, $(13-1)| 60$ , and $33 = 2\cdot 13 + 7$ , so that $T \equiv 7 - 2 \equiv 5$ mod 13.

• $p = 17$ . This time $(17-1)\not | 60$ . We see that adding $34^{60}$ will not affect the sum modulo 17, and that gives us $34 = 2\cdot 17 + 0$ , so that $T \equiv 0$ mod 17.

Here we can stop, because we have found that $\boxed{17}\ |\ T$ .

Since $(p - 1)|60$ is true for every prime p less than 17, $1^{60} + \cdots + {33}^{60} \equiv 33 - \lfloor \frac{33}{p} \rfloor$ (mod $p$ )

Now $33 \equiv \lfloor \frac{33}{p} \rfloor$ (mod $p$ ), and this is false for every prime p less than 17.

Prime numbers have a general property:

$1^n + 2^n + \cdots + {(p-1)}^n \equiv 0$ (mod p) iff $(p-1) \nmid n$

Since $(17 - 1) \nmid 60$

$1^{60}+2^{60} + 3^{60}+ \cdots + 33^{60} \equiv 2(1^{60}+2^{60} + 3^{60}+ \cdots + 16^{60}) \equiv 0$ (mod 17)

And therefore $\boxed{17}$ is our answer.