Mixing
![If $f,g:Eto E$, then prove that $gcirc f=0 Longleftrightarrow operatornameIm fsubset ker g$ [duplicate]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Prove that there is no positive integer $n$ such that $1^2000 + 2^2000 + ldots + n^2000$ is prime.
Clash Royale CLAN TAG#URR8PPP
up vote
15
down vote
favorite
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!
prime-numbers
edited Jul 19 at 16:50
Peter
45.1k939119
asked Jul 19 at 13:36
Iulian Oleniuc
3619
 |Â
show 2 more comments
up vote
15
down vote
favorite
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!
prime-numbers
edited Jul 19 at 16:50
Peter
45.1k939119
asked Jul 19 at 13:36
Iulian Oleniuc
3619
Is it true that $sum_k=1^nk^p+1$ is a non-prime for every prime $p$ greater than $3$?
– uniquesolution
Jul 19 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 at 13:59
@prog_SAHIL Not necessarily. What you just thought would be true when $n equiv 1 pmod 4$
– Mathejunior
Jul 19 at 14:13
6
Where did you find this problem?
– Oldboy
Jul 19 at 14:33
1
@Peter The quantity is always divisible by $fracngcd(n, 2001!)$, so your statement is true in all but at most finitely many cases.
– Dylan
Jul 20 at 9:12
 |Â
show 2 more comments
up vote
15
down vote
favorite
up vote
15
down vote
favorite
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!
prime-numbers
edited Jul 19 at 16:50
Peter
45.1k939119
asked Jul 19 at 13:36
Iulian Oleniuc
3619
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!
prime-numbers
edited Jul 19 at 16:50
Peter
45.1k939119
asked Jul 19 at 13:36
Iulian Oleniuc
3619
edited Jul 19 at 16:50
Peter
45.1k939119
edited Jul 19 at 16:50
Peter
45.1k939119
edited Jul 19 at 16:50
Peter
45.1k939119
45.1k939119
asked Jul 19 at 13:36
Iulian Oleniuc
3619
asked Jul 19 at 13:36
Iulian Oleniuc
3619
asked Jul 19 at 13:36
Iulian Oleniuc
3619
3619
Is it true that $sum_k=1^nk^p+1$ is a non-prime for every prime $p$ greater than $3$?
– uniquesolution
Jul 19 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 at 13:59
@prog_SAHIL Not necessarily. What you just thought would be true when $n equiv 1 pmod 4$
– Mathejunior
Jul 19 at 14:13
6
Where did you find this problem?
– Oldboy
Jul 19 at 14:33
1
@Peter The quantity is always divisible by $fracngcd(n, 2001!)$, so your statement is true in all but at most finitely many cases.
– Dylan
Jul 20 at 9:12
 |Â
show 2 more comments
Is it true that $sum_k=1^nk^p+1$ is a non-prime for every prime $p$ greater than $3$?
– uniquesolution
Jul 19 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 at 13:59
@prog_SAHIL Not necessarily. What you just thought would be true when $n equiv 1 pmod 4$
– Mathejunior
Jul 19 at 14:13
6
Where did you find this problem?
– Oldboy
Jul 19 at 14:33
1
@Peter The quantity is always divisible by $fracngcd(n, 2001!)$, so your statement is true in all but at most finitely many cases.
– Dylan
Jul 20 at 9:12
Is it true that $sum_k=1^nk^p+1$ is a non-prime for every prime $p$ greater than $3$?
– uniquesolution
Jul 19 at 13:54
Is it true that $sum_k=1^nk^p+1$ is a non-prime for every prime $p$ greater than $3$?
– uniquesolution
Jul 19 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 at 13:59
@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 at 13:59
@prog_SAHIL Not necessarily. What you just thought would be true when $n equiv 1 pmod 4$
– Mathejunior
Jul 19 at 14:13
@prog_SAHIL Not necessarily. What you just thought would be true when $n equiv 1 pmod 4$
– Mathejunior
Jul 19 at 14:13
6
6
Where did you find this problem?
– Oldboy
Jul 19 at 14:33
Where did you find this problem?
– Oldboy
Jul 19 at 14:33
1
1
@Peter The quantity is always divisible by $fracngcd(n, 2001!)$, so your statement is true in all but at most finitely many cases.
– Dylan
Jul 20 at 9:12
@Peter The quantity is always divisible by $fracngcd(n, 2001!)$, so your statement is true in all but at most finitely many cases.
– Dylan
Jul 20 at 9:12
 |Â
show 2 more comments
1 Answer
1
active
oldest
votes
up vote
8
down vote
accepted
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 $fracnp$ 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.
answered Jul 19 at 14:44
Dylan
5,67231134
1
How so is it clear that for $nleq 2000$ that the sum is not a prime? Any hints?
– quantum
Jul 19 at 17:34
1
@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 at 11:08
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
accepted
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 $fracnp$ 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.
answered Jul 19 at 14:44
Dylan
5,67231134
1
How so is it clear that for $nleq 2000$ that the sum is not a prime? Any hints?
– quantum
Jul 19 at 17:34
1
@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 at 11:08
add a comment |Â
up vote
8
down vote
accepted
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 $fracnp$ 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.
answered Jul 19 at 14:44
Dylan
5,67231134
1
How so is it clear that for $nleq 2000$ that the sum is not a prime? Any hints?
– quantum
Jul 19 at 17:34
1
@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 at 11:08
add a comment |Â
up vote
8
down vote
accepted
up vote
8
down vote
accepted
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 $fracnp$ 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.
answered Jul 19 at 14:44
Dylan
5,67231134
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 $fracnp$ 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.
answered Jul 19 at 14:44
Dylan
5,67231134
edited Jul 19 at 15:57
answered Jul 19 at 14:44
Dylan
5,67231134
answered Jul 19 at 14:44
Dylan
5,67231134
answered Jul 19 at 14:44
Dylan
5,67231134
5,67231134
1
How so is it clear that for $nleq 2000$ that the sum is not a prime? Any hints?
– quantum
Jul 19 at 17:34
1
@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 at 11:08
add a comment |Â
1
How so is it clear that for $nleq 2000$ that the sum is not a prime? Any hints?
– quantum
Jul 19 at 17:34
1
@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 at 11:08
1
1
How so is it clear that for $nleq 2000$ that the sum is not a prime? Any hints?
– quantum
Jul 19 at 17:34
How so is it clear that for $nleq 2000$ that the sum is not a prime? Any hints?
– quantum
Jul 19 at 17:34
1
1
@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 at 11:08
@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 at 11:08
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856639%2fprove-that-there-is-no-positive-integer-n-such-that-12000-22000-ld%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Is it true that $sum_k=1^nk^p+1$ is a non-prime for every prime $p$ greater than $3$?
– uniquesolution
Jul 19 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 at 13:59
@prog_SAHIL Not necessarily. What you just thought would be true when $n equiv 1 pmod 4$
– Mathejunior
Jul 19 at 14:13
6
Where did you find this problem?
– Oldboy
Jul 19 at 14:33
1
@Peter The quantity is always divisible by $fracngcd(n, 2001!)$, so your statement is true in all but at most finitely many cases.
– Dylan
Jul 20 at 9:12