How to test if $n!+1$ is prime or not?
up vote
3
down vote
favorite
For $n=0,1,2,3,11,27,37,41,73,77,116,154,320,340,399,427,872,1477,6380,26951,...,$
$n!+1$ is prime. But how can you prove that this is always the case? Especially for the larger ones.
For example $1477!+1$ this number has several hundert digits, I know we can apply stochastic factor or prime algorithms, but how can you do the final proof without testing all factors?
prime-numbers pseudoprimes
edited Nov 21 at 11:50
Klangen
1,32811130
asked Jul 13 '16 at 8:22
user160069
370310
add a comment |
up vote
3
down vote
favorite
For $n=0,1,2,3,11,27,37,41,73,77,116,154,320,340,399,427,872,1477,6380,26951,...,$
$n!+1$ is prime. But how can you prove that this is always the case? Especially for the larger ones.
For example $1477!+1$ this number has several hundert digits, I know we can apply stochastic factor or prime algorithms, but how can you do the final proof without testing all factors?
prime-numbers pseudoprimes
edited Nov 21 at 11:50
Klangen
1,32811130
asked Jul 13 '16 at 8:22
user160069
370310
$n!+1$ isn't prime always. So what are you trying to prove? Or are you asking for some way to check whether for a particular $n$, $n!+1$ is prime?
– Aritra Das
Jul 13 '16 at 8:28
So basically you're asking how people test for primality. Well, if you want to be sure, you need to use a deterministic primality test. Checking all the factors is such a test, but it is very slow. You can read here for more information on some other tests, but they can be very difficult. en.wikipedia.org/wiki/Primality_test
– Mathematician 42
Jul 13 '16 at 8:31
2
Let $m=n!+1.$ Since you have the complete prime factorization of $m-1$ you can use Theorem 1 (improved Lucas test) from primes.utm.edu/prove/prove3_1.html to computionally test the primality.
– gammatester
Jul 13 '16 at 8:32
Actually both, how can you prove $n!+1$ is prime or how can you prove $n!+1$ isn't prime, without stochastic tests such as PollardRho etc.
– user160069
Jul 13 '16 at 8:32
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
For $n=0,1,2,3,11,27,37,41,73,77,116,154,320,340,399,427,872,1477,6380,26951,...,$
$n!+1$ is prime. But how can you prove that this is always the case? Especially for the larger ones.
For example $1477!+1$ this number has several hundert digits, I know we can apply stochastic factor or prime algorithms, but how can you do the final proof without testing all factors?
prime-numbers pseudoprimes
edited Nov 21 at 11:50
Klangen
1,32811130
asked Jul 13 '16 at 8:22
user160069
370310
For $n=0,1,2,3,11,27,37,41,73,77,116,154,320,340,399,427,872,1477,6380,26951,...,$
$n!+1$ is prime. But how can you prove that this is always the case? Especially for the larger ones.
For example $1477!+1$ this number has several hundert digits, I know we can apply stochastic factor or prime algorithms, but how can you do the final proof without testing all factors?
prime-numbers pseudoprimes
prime-numbers pseudoprimes
edited Nov 21 at 11:50
Klangen
1,32811130
asked Jul 13 '16 at 8:22
user160069
370310
edited Nov 21 at 11:50
Klangen
1,32811130
asked Jul 13 '16 at 8:22
user160069
370310
edited Nov 21 at 11:50
Klangen
1,32811130
edited Nov 21 at 11:50
Klangen
1,32811130
edited Nov 21 at 11:50
Klangen
1,32811130
1,32811130
asked Jul 13 '16 at 8:22
user160069
370310
asked Jul 13 '16 at 8:22
user160069
370310
asked Jul 13 '16 at 8:22
user160069
370310
370310
$n!+1$ isn't prime always. So what are you trying to prove? Or are you asking for some way to check whether for a particular $n$, $n!+1$ is prime?
– Aritra Das
Jul 13 '16 at 8:28
So basically you're asking how people test for primality. Well, if you want to be sure, you need to use a deterministic primality test. Checking all the factors is such a test, but it is very slow. You can read here for more information on some other tests, but they can be very difficult. en.wikipedia.org/wiki/Primality_test
– Mathematician 42
Jul 13 '16 at 8:31
2
Let $m=n!+1.$ Since you have the complete prime factorization of $m-1$ you can use Theorem 1 (improved Lucas test) from primes.utm.edu/prove/prove3_1.html to computionally test the primality.
– gammatester
Jul 13 '16 at 8:32
Actually both, how can you prove $n!+1$ is prime or how can you prove $n!+1$ isn't prime, without stochastic tests such as PollardRho etc.
– user160069
Jul 13 '16 at 8:32
add a comment |
$n!+1$ isn't prime always. So what are you trying to prove? Or are you asking for some way to check whether for a particular $n$, $n!+1$ is prime?
– Aritra Das
Jul 13 '16 at 8:28
So basically you're asking how people test for primality. Well, if you want to be sure, you need to use a deterministic primality test. Checking all the factors is such a test, but it is very slow. You can read here for more information on some other tests, but they can be very difficult. en.wikipedia.org/wiki/Primality_test
– Mathematician 42
Jul 13 '16 at 8:31
2
Let $m=n!+1.$ Since you have the complete prime factorization of $m-1$ you can use Theorem 1 (improved Lucas test) from primes.utm.edu/prove/prove3_1.html to computionally test the primality.
– gammatester
Jul 13 '16 at 8:32
Actually both, how can you prove $n!+1$ is prime or how can you prove $n!+1$ isn't prime, without stochastic tests such as PollardRho etc.
– user160069
Jul 13 '16 at 8:32
$n!+1$ isn't prime always. So what are you trying to prove? Or are you asking for some way to check whether for a particular $n$, $n!+1$ is prime?
– Aritra Das
Jul 13 '16 at 8:28
$n!+1$ isn't prime always. So what are you trying to prove? Or are you asking for some way to check whether for a particular $n$, $n!+1$ is prime?
– Aritra Das
Jul 13 '16 at 8:28
So basically you're asking how people test for primality. Well, if you want to be sure, you need to use a deterministic primality test. Checking all the factors is such a test, but it is very slow. You can read here for more information on some other tests, but they can be very difficult. en.wikipedia.org/wiki/Primality_test
– Mathematician 42
Jul 13 '16 at 8:31
So basically you're asking how people test for primality. Well, if you want to be sure, you need to use a deterministic primality test. Checking all the factors is such a test, but it is very slow. You can read here for more information on some other tests, but they can be very difficult. en.wikipedia.org/wiki/Primality_test
– Mathematician 42
Jul 13 '16 at 8:31
2
2
Let $m=n!+1.$ Since you have the complete prime factorization of $m-1$ you can use Theorem 1 (improved Lucas test) from primes.utm.edu/prove/prove3_1.html to computionally test the primality.
– gammatester
Jul 13 '16 at 8:32
Let $m=n!+1.$ Since you have the complete prime factorization of $m-1$ you can use Theorem 1 (improved Lucas test) from primes.utm.edu/prove/prove3_1.html to computionally test the primality.
– gammatester
Jul 13 '16 at 8:32
Actually both, how can you prove $n!+1$ is prime or how can you prove $n!+1$ isn't prime, without stochastic tests such as PollardRho etc.
– user160069
Jul 13 '16 at 8:32
Actually both, how can you prove $n!+1$ is prime or how can you prove $n!+1$ isn't prime, without stochastic tests such as PollardRho etc.
– user160069
Jul 13 '16 at 8:32
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1857929%2fhow-to-test-if-n1-is-prime-or-not%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$n!+1$ isn't prime always. So what are you trying to prove? Or are you asking for some way to check whether for a particular $n$, $n!+1$ is prime?
– Aritra Das
Jul 13 '16 at 8:28
So basically you're asking how people test for primality. Well, if you want to be sure, you need to use a deterministic primality test. Checking all the factors is such a test, but it is very slow. You can read here for more information on some other tests, but they can be very difficult. en.wikipedia.org/wiki/Primality_test
– Mathematician 42
Jul 13 '16 at 8:31
2
Let $m=n!+1.$ Since you have the complete prime factorization of $m-1$ you can use Theorem 1 (improved Lucas test) from primes.utm.edu/prove/prove3_1.html to computionally test the primality.
– gammatester
Jul 13 '16 at 8:32
Actually both, how can you prove $n!+1$ is prime or how can you prove $n!+1$ isn't prime, without stochastic tests such as PollardRho etc.
– user160069
Jul 13 '16 at 8:32