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!

Solution 1:

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.