15
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Is it true that $\sum_{k=1}^nk^{p+1}$ is a non-prime for every prime $p$ greater than $3$? $\endgroup$ – uniquesolution Jul 19 '18 at 13:54
  • $\begingroup$ @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. $\endgroup$ – prog_SAHIL Jul 19 '18 at 13:59
  • $\begingroup$ @prog_SAHIL Not necessarily. What you just thought would be true when $n \equiv 1 \pmod 4$ $\endgroup$ – Mathejunior Jul 19 '18 at 14:13
  • 6
    $\begingroup$ Where did you find this problem? $\endgroup$ – Oldboy Jul 19 '18 at 14:33
  • 1
    $\begingroup$ @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. $\endgroup$ – Dylan Jul 20 '18 at 9:12
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How so is it clear that for $n\leq 2000$ that the sum is not a prime? Any hints? $\endgroup$ – quantum Jul 19 '18 at 17:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Dylan Jul 20 '18 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.