# Prove that there is no positive integer $n$ such that $1^{2000} + 2^{2000} + \ldots + n^{2000}$ is prime.

Prove that there is no positive integer $n$ such that the following number is prime: $$S_n = 1^{2000} + 2^{2000} + \ldots + n^{2000}$$

I was thinking about the last digit of the number. For certain values of $n$, the last digit of $S$ is even, so $S$ can't be prime. But that's not enough. Can you give me a hint, please? Thanks!

• Is it true that $\sum_{k=1}^nk^{p+1}$ is a non-prime for every prime $p$ greater than $3$? – uniquesolution Jul 19 '18 at 13:54
• @lulu, I was thinking that all the odd numbers will yield odd last digits that form even. (but there need to even odd terms for that.) I can be hasty at times. – prog_SAHIL Jul 19 '18 at 13:59
• @prog_SAHIL Not necessarily. What you just thought would be true when $n \equiv 1 \pmod 4$ – Mathejunior Jul 19 '18 at 14:13
• Where did you find this problem? – Oldboy Jul 19 '18 at 14:33
• @Peter The quantity is always divisible by $\frac{n}{\gcd(n, 2001!)}$, so your statement is true in all but at most finitely many cases. – Dylan Jul 20 '18 at 9:12

This is not a complete answer, but it does reduce the problem to checking a finite number ($512$, in fact) of cases. [This is no longer a case. I used a computer to check the remaining cases, and it confirmed that $f(n)$ is never prime.]

Let $$f(n) = 1^{2000} + 2^{2000} + \dots + n^{2000}.$$

It is possible to show that if $p$ is a prime, and $k < p - 1$, then $$1^k + 2^k + \dots + p^k$$ is divisible by $p$. It follows that if $n$ has any prime factors $p$ such that $p > 2001$, then $p | f(n)$, and so $f(n)$ is not prime. (We have that $f(n) \neq p$ since $f(n) > n^{2000} > n \geq p$.)

(We can break the sum $$1^{2000} + 2^{2000} + \dots + n^{2000}$$ up into $\frac{n}{p}$ blocks where sum of each block is congruent modulo $p$ to $$1^{2000} + 2^{2000} + \dots + p^{2000} \equiv 0 \pmod p$$ )

The only cases that remain is when all of the prime factors of $n$ are less than $2000$. Suppose that $p \mid n$, and let $2000 = (p - 1) q + r$ where $r < p - 1$.

We then have that $$1^{2000} + 2^{2000} + \dots + p^{2000} \equiv 1^r + 2^r + \dots + (p - 1)^r \pmod p$$ As long as $r \neq 0$, we have that this is divisible by $p$. Thus $f(n)$ is divisible by $p$.

We thus have to consider the case where $p - 1 \mid 2000$. Thus we can reduce to the case where the only prime factors of $n$ are $2, 3, 5, 11, 17, 41, 101, 251, 401$.

Now suppose that there is a prime $p$ such that $p^2 \mid n$. We have that $$1^{2000} + 2^{2000} + \dots + (p^2)^{2000} \equiv p \left( 1^{2000} + 2^{2000} + \dots + p^{2000} \right) \equiv 0 \pmod p.$$

As before, this implies that $p \mid f(n)$. We can thus assume that $n$ is square-free.

Thus if $f(n)$ is a prime, then we must have that $n$ is square-free, and its only prime factors are from among $2, 3, 5, 11, 17, 41, 101, 251, 401$. This leaves us with a finite number of cases to check.

Some of these are easy to rule out. e.g. If $n$ is not divisible by $2$ and has an odd number of factors from among $3, 11, 251$, then we have that $n \equiv 3 \pmod 4$, and in this case we have that $f(n)$ is even.

Perhaps similar arguments work for numbers like $$f( 2 \times 3 \times 5 \times 11 \times 17 \times 41 \times 101 \times 251 \times 401)$$

I don't think that it would be feasible to check if this number is prime unless there is some small prime which divides it.

Edit: In fact, a similar argument to the one above shows that if $n \equiv -1 \pmod p$ for any prime $p$ which is not among $2, 3, 5, 11, 17, 41, 101, 251, 401$, then $f(n)$ is divisible by $p$. So, in fact $$f( 2 \times 3 \times 5 \times 11 \times 17 \times 41 \times 101 \times 251 \times 401)$$ is not a prime.

This is because we also have that $$1^{2000} + 2^{2000} + \dots + (p - 1)^{2000} \equiv 0 \pmod p$$ in the cases where $2000 < p - 1$.

I've written a python script to check that the only natural numbers $n$ where the above considerations are not sufficient to verify that $f(n)$ is not prime are $$1, 2, 3, 5, 10, 15, 11, 33, 17, 255, 374, 101, 8282, 1039391, 13634$$

I then checked whether $f(n)$ is prime for these numbers using trial division. It is indeed the case that $f(n)$ is not prime in any of these cases, and so $f(n)$ is never prime.

• How so is it clear that for $n\leq 2000$ that the sum is not a prime? Any hints? – quantum Jul 19 '18 at 17:34
• @quantum Some of it is covered in the proof above (i.e. the cases where $n$ is not a square-free natural number whose only factors are among $2, 3, 5, 11, 17, 41, 101, 251, 401$) You can rule out all of the possibilities except those at the bottom of the post by using the fact that if $n + 1$ is divisible by a prime $p$ that is not on our list above, then $f(n)$ is divisible by $p$. In fact, you can then rule out every case except for $n = 1, 2, 5, 10, 33, 101, 8282$ by using that if $p^2 \mid n + 1$ then $p \mid f(n)$. For the rest, I calculated $f(n)$ explicitly and used trial division. – Dylan Jul 20 '18 at 11:08