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
Flermat
1,28311129
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
Flermat
1,28311129
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
Flermat
1,28311129
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
Flermat
1,28311129
asked Jul 13 '16 at 8:22
user160069
370310
edited Nov 21 at 11:50
Flermat
1,28311129
asked Jul 13 '16 at 8:22
user160069
370310
edited Nov 21 at 11:50
Flermat
1,28311129
edited Nov 21 at 11:50
Flermat
1,28311129
edited Nov 21 at 11:50
Flermat
1,28311129
1,28311129
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
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