Finding $p$ such that $pn pm 1$ is prime for a fixed $n$
$begingroup$
I want to find a prime $p$ such that $pn pm 1$ is prime for some fixed $n$.
Examples of $n$ are $1683$ or $99617$. Any $p$ will do, it doesn't need to be the smallest possible value.
I have tried bruteforcing a few examples. My method is to try successively larger values of $p$ until a prime is produced. However, for some values of $n$ I have tried primes up to $100,000,000$ (one hundred million) and still not found an answer.
I've tried searching online, but I haven't found an answer. I'm not sure I have the right terminology. The closest result I've found are Sophie Germain primes, which are the special case of $n=2$.
EDIT: To be clear, my question is "Is there a general method that I can plug a value of $n$ into and it will produce a prime $p$ so that the above is satisfied?"
number-theory prime-numbers sieve-theory
asked Dec 10 '18 at 23:33
spyr03spyr03
519518
$endgroup$
|
show 2 more comments
$begingroup$
I want to find a prime $p$ such that $pn pm 1$ is prime for some fixed $n$.
Examples of $n$ are $1683$ or $99617$. Any $p$ will do, it doesn't need to be the smallest possible value.
I have tried bruteforcing a few examples. My method is to try successively larger values of $p$ until a prime is produced. However, for some values of $n$ I have tried primes up to $100,000,000$ (one hundred million) and still not found an answer.
I've tried searching online, but I haven't found an answer. I'm not sure I have the right terminology. The closest result I've found are Sophie Germain primes, which are the special case of $n=2$.
EDIT: To be clear, my question is "Is there a general method that I can plug a value of $n$ into and it will produce a prime $p$ so that the above is satisfied?"
number-theory prime-numbers sieve-theory
asked Dec 10 '18 at 23:33
spyr03spyr03
519518
$endgroup$
$begingroup$
I don't understand your question. Right now, it sounds like you want to fix some $n$, and then find some prime $p$ such that either $pn+1$ or $pn-1$ is also prime. Then what? Are you asking if this is always possible? What is the actual question?
$endgroup$
– davidlowryduda♦
Dec 10 '18 at 23:37
$begingroup$
I assume OP is looking at a sort of generalization of the Sophie Germain primes. Choose a specific $n$, say $n=3$. Then for prime $p$, he wants to see which among $3p + 1$ are also prime, for example, which he seems to be doing via a script that checks primes $p$ up to $10^8$.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:39
$begingroup$
@davidlowryduda I'll try and edit the question to make it more clear. You are correct, I want to find some $p$ so that either $pn - 1$ or $pn + 1$ is prime. I'd like to be able to find the value in general for any $n$.
$endgroup$
– spyr03
Dec 10 '18 at 23:39
1
$begingroup$
Aside from that, I wonder if there's some sort of pattern in these $n$ that results in no such primes (at least in your investigations). Of course it could be possible that the primes that result are very large, but who knows. As one example of $n$ which won't work: It should be clear that $n$ which are odd won't work for odd primes $p$: $np$ will then be odd, and then $pm 1$ will be even, i.e. composite. So unless $2n pm 1$ is prime in those cases, $n$ odd never generates such a prime.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:42
1
$begingroup$
@EeveeTrainer Oh, I completely missed that... That would explain why I haven't found an answer for $1683$. I guess we can assume $n$ is even then. :/
$endgroup$
– spyr03
Dec 10 '18 at 23:51
|
show 2 more comments
$begingroup$
I want to find a prime $p$ such that $pn pm 1$ is prime for some fixed $n$.
Examples of $n$ are $1683$ or $99617$. Any $p$ will do, it doesn't need to be the smallest possible value.
I have tried bruteforcing a few examples. My method is to try successively larger values of $p$ until a prime is produced. However, for some values of $n$ I have tried primes up to $100,000,000$ (one hundred million) and still not found an answer.
I've tried searching online, but I haven't found an answer. I'm not sure I have the right terminology. The closest result I've found are Sophie Germain primes, which are the special case of $n=2$.
EDIT: To be clear, my question is "Is there a general method that I can plug a value of $n$ into and it will produce a prime $p$ so that the above is satisfied?"
number-theory prime-numbers sieve-theory
asked Dec 10 '18 at 23:33
spyr03spyr03
519518
$endgroup$
I want to find a prime $p$ such that $pn pm 1$ is prime for some fixed $n$.
Examples of $n$ are $1683$ or $99617$. Any $p$ will do, it doesn't need to be the smallest possible value.
I have tried bruteforcing a few examples. My method is to try successively larger values of $p$ until a prime is produced. However, for some values of $n$ I have tried primes up to $100,000,000$ (one hundred million) and still not found an answer.
I've tried searching online, but I haven't found an answer. I'm not sure I have the right terminology. The closest result I've found are Sophie Germain primes, which are the special case of $n=2$.
EDIT: To be clear, my question is "Is there a general method that I can plug a value of $n$ into and it will produce a prime $p$ so that the above is satisfied?"
number-theory prime-numbers sieve-theory
number-theory prime-numbers sieve-theory
asked Dec 10 '18 at 23:33
spyr03spyr03
519518
asked Dec 10 '18 at 23:33
spyr03spyr03
519518
edited Dec 10 '18 at 23:42
spyr03
asked Dec 10 '18 at 23:33
spyr03spyr03
519518
asked Dec 10 '18 at 23:33
spyr03spyr03
519518
asked Dec 10 '18 at 23:33
spyr03spyr03
519518
519518
$begingroup$
I don't understand your question. Right now, it sounds like you want to fix some $n$, and then find some prime $p$ such that either $pn+1$ or $pn-1$ is also prime. Then what? Are you asking if this is always possible? What is the actual question?
$endgroup$
– davidlowryduda♦
Dec 10 '18 at 23:37
$begingroup$
I assume OP is looking at a sort of generalization of the Sophie Germain primes. Choose a specific $n$, say $n=3$. Then for prime $p$, he wants to see which among $3p + 1$ are also prime, for example, which he seems to be doing via a script that checks primes $p$ up to $10^8$.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:39
$begingroup$
@davidlowryduda I'll try and edit the question to make it more clear. You are correct, I want to find some $p$ so that either $pn - 1$ or $pn + 1$ is prime. I'd like to be able to find the value in general for any $n$.
$endgroup$
– spyr03
Dec 10 '18 at 23:39
1
$begingroup$
Aside from that, I wonder if there's some sort of pattern in these $n$ that results in no such primes (at least in your investigations). Of course it could be possible that the primes that result are very large, but who knows. As one example of $n$ which won't work: It should be clear that $n$ which are odd won't work for odd primes $p$: $np$ will then be odd, and then $pm 1$ will be even, i.e. composite. So unless $2n pm 1$ is prime in those cases, $n$ odd never generates such a prime.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:42
1
$begingroup$
@EeveeTrainer Oh, I completely missed that... That would explain why I haven't found an answer for $1683$. I guess we can assume $n$ is even then. :/
$endgroup$
– spyr03
Dec 10 '18 at 23:51
|
show 2 more comments
$begingroup$
I don't understand your question. Right now, it sounds like you want to fix some $n$, and then find some prime $p$ such that either $pn+1$ or $pn-1$ is also prime. Then what? Are you asking if this is always possible? What is the actual question?
$endgroup$
– davidlowryduda♦
Dec 10 '18 at 23:37
$begingroup$
I assume OP is looking at a sort of generalization of the Sophie Germain primes. Choose a specific $n$, say $n=3$. Then for prime $p$, he wants to see which among $3p + 1$ are also prime, for example, which he seems to be doing via a script that checks primes $p$ up to $10^8$.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:39
$begingroup$
@davidlowryduda I'll try and edit the question to make it more clear. You are correct, I want to find some $p$ so that either $pn - 1$ or $pn + 1$ is prime. I'd like to be able to find the value in general for any $n$.
$endgroup$
– spyr03
Dec 10 '18 at 23:39
1
$begingroup$
Aside from that, I wonder if there's some sort of pattern in these $n$ that results in no such primes (at least in your investigations). Of course it could be possible that the primes that result are very large, but who knows. As one example of $n$ which won't work: It should be clear that $n$ which are odd won't work for odd primes $p$: $np$ will then be odd, and then $pm 1$ will be even, i.e. composite. So unless $2n pm 1$ is prime in those cases, $n$ odd never generates such a prime.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:42
1
$begingroup$
@EeveeTrainer Oh, I completely missed that... That would explain why I haven't found an answer for $1683$. I guess we can assume $n$ is even then. :/
$endgroup$
– spyr03
Dec 10 '18 at 23:51
$begingroup$
I don't understand your question. Right now, it sounds like you want to fix some $n$, and then find some prime $p$ such that either $pn+1$ or $pn-1$ is also prime. Then what? Are you asking if this is always possible? What is the actual question?
$endgroup$
– davidlowryduda♦
Dec 10 '18 at 23:37
$begingroup$
I don't understand your question. Right now, it sounds like you want to fix some $n$, and then find some prime $p$ such that either $pn+1$ or $pn-1$ is also prime. Then what? Are you asking if this is always possible? What is the actual question?
$endgroup$
– davidlowryduda♦
Dec 10 '18 at 23:37
$begingroup$
I assume OP is looking at a sort of generalization of the Sophie Germain primes. Choose a specific $n$, say $n=3$. Then for prime $p$, he wants to see which among $3p + 1$ are also prime, for example, which he seems to be doing via a script that checks primes $p$ up to $10^8$.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:39
$begingroup$
I assume OP is looking at a sort of generalization of the Sophie Germain primes. Choose a specific $n$, say $n=3$. Then for prime $p$, he wants to see which among $3p + 1$ are also prime, for example, which he seems to be doing via a script that checks primes $p$ up to $10^8$.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:39
$begingroup$
@davidlowryduda I'll try and edit the question to make it more clear. You are correct, I want to find some $p$ so that either $pn - 1$ or $pn + 1$ is prime. I'd like to be able to find the value in general for any $n$.
$endgroup$
– spyr03
Dec 10 '18 at 23:39
$begingroup$
@davidlowryduda I'll try and edit the question to make it more clear. You are correct, I want to find some $p$ so that either $pn - 1$ or $pn + 1$ is prime. I'd like to be able to find the value in general for any $n$.
$endgroup$
– spyr03
Dec 10 '18 at 23:39
1
1
$begingroup$
Aside from that, I wonder if there's some sort of pattern in these $n$ that results in no such primes (at least in your investigations). Of course it could be possible that the primes that result are very large, but who knows. As one example of $n$ which won't work: It should be clear that $n$ which are odd won't work for odd primes $p$: $np$ will then be odd, and then $pm 1$ will be even, i.e. composite. So unless $2n pm 1$ is prime in those cases, $n$ odd never generates such a prime.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:42
$begingroup$
Aside from that, I wonder if there's some sort of pattern in these $n$ that results in no such primes (at least in your investigations). Of course it could be possible that the primes that result are very large, but who knows. As one example of $n$ which won't work: It should be clear that $n$ which are odd won't work for odd primes $p$: $np$ will then be odd, and then $pm 1$ will be even, i.e. composite. So unless $2n pm 1$ is prime in those cases, $n$ odd never generates such a prime.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:42
1
1
$begingroup$
@EeveeTrainer Oh, I completely missed that... That would explain why I haven't found an answer for $1683$. I guess we can assume $n$ is even then. :/
$endgroup$
– spyr03
Dec 10 '18 at 23:51
$begingroup$
@EeveeTrainer Oh, I completely missed that... That would explain why I haven't found an answer for $1683$. I guess we can assume $n$ is even then. :/
$endgroup$
– spyr03
Dec 10 '18 at 23:51
|
show 2 more comments
2 Answers
2
active
oldest
votes
$begingroup$
To be precise, there is no "general method," to know which $p$ will yield $pnpm 1$ prime for any given $n$, however there are many ways to check the primality of each individual $pnpm 1$, even for very large values. The most computationally complex way to check the primality of any number is from AKS. Take a coprime $a$; $pnpm 1$ is prime if and only if
$(x+a)^{pnpm 1}equiv (x^{pnpm 1}+a)mod n$. [1]
However, this method gets prohibitive for larger values. For larger values, if you restrict the values of $n$ and the $pm$ to only a $+$, you can find primes of this form quite easily. When $n=2^x$ (and it is not a base 3 Fermat divisor), that is for $2^np+1$, we know that it is prime if and only if
$3^{2^{n-1}p}equiv -1mod 2^np+1$. [2]
When $2p+1>sqrt{np+1}$, we know that it is prime if for some $a$,
$a^{frac{np}{2}}equiv -1mod np+1$ and $a^{frac{n}{2}}notequiv -1mod np+1$.[3]
If there is any prime $q$ of $n$ such that $2q+1>sqrt{pn+1}$, then the above formula will work with $q$ instead of $p$.There are more primality tests of similar forms, such as testing $np^a+1$, for $p^a>n$.
[1] https://web.archive.org/web/20140219064936/http://www.dm.unito.it/~cerruti/ac/aks-crandall.pdf
[2]https://peerj.com/manuscripts/33147/
[3]https://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf
answered Dec 18 '18 at 21:46
Tejas RaoTejas Rao
16611
$endgroup$
add a comment |
$begingroup$
I don't have a 50 reputation yet, so I am providing this as an answer. First, if there was a "general" way to find primes as you request, then this would provide a specific way to find prime numbers of basically any size, which as far as I know nobody has determined yet. Nonetheless, note that although any even value of $n$ will work, as the comments above stated, it will generally be easiest to find a prime if $n$ has many small, unique prime factors, especially if it's a primorial (i.e., the product of all primes up to a given prime, such as 2, 6, 30, 210, etc.). This is because $pn pm 1$ will then be relatively prime to all of those factors and, thus, it's more likely that one or both values are prime.
answered Dec 18 '18 at 21:26
John OmielanJohn Omielan
2,046210
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3034646%2ffinding-p-such-that-pn-pm-1-is-prime-for-a-fixed-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
To be precise, there is no "general method," to know which $p$ will yield $pnpm 1$ prime for any given $n$, however there are many ways to check the primality of each individual $pnpm 1$, even for very large values. The most computationally complex way to check the primality of any number is from AKS. Take a coprime $a$; $pnpm 1$ is prime if and only if
$(x+a)^{pnpm 1}equiv (x^{pnpm 1}+a)mod n$. [1]
However, this method gets prohibitive for larger values. For larger values, if you restrict the values of $n$ and the $pm$ to only a $+$, you can find primes of this form quite easily. When $n=2^x$ (and it is not a base 3 Fermat divisor), that is for $2^np+1$, we know that it is prime if and only if
$3^{2^{n-1}p}equiv -1mod 2^np+1$. [2]
When $2p+1>sqrt{np+1}$, we know that it is prime if for some $a$,
$a^{frac{np}{2}}equiv -1mod np+1$ and $a^{frac{n}{2}}notequiv -1mod np+1$.[3]
If there is any prime $q$ of $n$ such that $2q+1>sqrt{pn+1}$, then the above formula will work with $q$ instead of $p$.There are more primality tests of similar forms, such as testing $np^a+1$, for $p^a>n$.
[1] https://web.archive.org/web/20140219064936/http://www.dm.unito.it/~cerruti/ac/aks-crandall.pdf
[2]https://peerj.com/manuscripts/33147/
[3]https://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf
answered Dec 18 '18 at 21:46
Tejas RaoTejas Rao
16611
$endgroup$
add a comment |
$begingroup$
To be precise, there is no "general method," to know which $p$ will yield $pnpm 1$ prime for any given $n$, however there are many ways to check the primality of each individual $pnpm 1$, even for very large values. The most computationally complex way to check the primality of any number is from AKS. Take a coprime $a$; $pnpm 1$ is prime if and only if
$(x+a)^{pnpm 1}equiv (x^{pnpm 1}+a)mod n$. [1]
However, this method gets prohibitive for larger values. For larger values, if you restrict the values of $n$ and the $pm$ to only a $+$, you can find primes of this form quite easily. When $n=2^x$ (and it is not a base 3 Fermat divisor), that is for $2^np+1$, we know that it is prime if and only if
$3^{2^{n-1}p}equiv -1mod 2^np+1$. [2]
When $2p+1>sqrt{np+1}$, we know that it is prime if for some $a$,
$a^{frac{np}{2}}equiv -1mod np+1$ and $a^{frac{n}{2}}notequiv -1mod np+1$.[3]
If there is any prime $q$ of $n$ such that $2q+1>sqrt{pn+1}$, then the above formula will work with $q$ instead of $p$.There are more primality tests of similar forms, such as testing $np^a+1$, for $p^a>n$.
[1] https://web.archive.org/web/20140219064936/http://www.dm.unito.it/~cerruti/ac/aks-crandall.pdf
[2]https://peerj.com/manuscripts/33147/
[3]https://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf
answered Dec 18 '18 at 21:46
Tejas RaoTejas Rao
16611
$endgroup$
add a comment |
$begingroup$
To be precise, there is no "general method," to know which $p$ will yield $pnpm 1$ prime for any given $n$, however there are many ways to check the primality of each individual $pnpm 1$, even for very large values. The most computationally complex way to check the primality of any number is from AKS. Take a coprime $a$; $pnpm 1$ is prime if and only if
$(x+a)^{pnpm 1}equiv (x^{pnpm 1}+a)mod n$. [1]
However, this method gets prohibitive for larger values. For larger values, if you restrict the values of $n$ and the $pm$ to only a $+$, you can find primes of this form quite easily. When $n=2^x$ (and it is not a base 3 Fermat divisor), that is for $2^np+1$, we know that it is prime if and only if
$3^{2^{n-1}p}equiv -1mod 2^np+1$. [2]
When $2p+1>sqrt{np+1}$, we know that it is prime if for some $a$,
$a^{frac{np}{2}}equiv -1mod np+1$ and $a^{frac{n}{2}}notequiv -1mod np+1$.[3]
If there is any prime $q$ of $n$ such that $2q+1>sqrt{pn+1}$, then the above formula will work with $q$ instead of $p$.There are more primality tests of similar forms, such as testing $np^a+1$, for $p^a>n$.
[1] https://web.archive.org/web/20140219064936/http://www.dm.unito.it/~cerruti/ac/aks-crandall.pdf
[2]https://peerj.com/manuscripts/33147/
[3]https://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf
answered Dec 18 '18 at 21:46
Tejas RaoTejas Rao
16611
$endgroup$
To be precise, there is no "general method," to know which $p$ will yield $pnpm 1$ prime for any given $n$, however there are many ways to check the primality of each individual $pnpm 1$, even for very large values. The most computationally complex way to check the primality of any number is from AKS. Take a coprime $a$; $pnpm 1$ is prime if and only if
$(x+a)^{pnpm 1}equiv (x^{pnpm 1}+a)mod n$. [1]
However, this method gets prohibitive for larger values. For larger values, if you restrict the values of $n$ and the $pm$ to only a $+$, you can find primes of this form quite easily. When $n=2^x$ (and it is not a base 3 Fermat divisor), that is for $2^np+1$, we know that it is prime if and only if
$3^{2^{n-1}p}equiv -1mod 2^np+1$. [2]
When $2p+1>sqrt{np+1}$, we know that it is prime if for some $a$,
$a^{frac{np}{2}}equiv -1mod np+1$ and $a^{frac{n}{2}}notequiv -1mod np+1$.[3]
If there is any prime $q$ of $n$ such that $2q+1>sqrt{pn+1}$, then the above formula will work with $q$ instead of $p$.There are more primality tests of similar forms, such as testing $np^a+1$, for $p^a>n$.
[1] https://web.archive.org/web/20140219064936/http://www.dm.unito.it/~cerruti/ac/aks-crandall.pdf
[2]https://peerj.com/manuscripts/33147/
[3]https://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf
answered Dec 18 '18 at 21:46
Tejas RaoTejas Rao
16611
answered Dec 18 '18 at 21:46
Tejas RaoTejas Rao
16611
answered Dec 18 '18 at 21:46
Tejas RaoTejas Rao
16611
answered Dec 18 '18 at 21:46
Tejas RaoTejas Rao
16611
16611
add a comment |
add a comment |
$begingroup$
I don't have a 50 reputation yet, so I am providing this as an answer. First, if there was a "general" way to find primes as you request, then this would provide a specific way to find prime numbers of basically any size, which as far as I know nobody has determined yet. Nonetheless, note that although any even value of $n$ will work, as the comments above stated, it will generally be easiest to find a prime if $n$ has many small, unique prime factors, especially if it's a primorial (i.e., the product of all primes up to a given prime, such as 2, 6, 30, 210, etc.). This is because $pn pm 1$ will then be relatively prime to all of those factors and, thus, it's more likely that one or both values are prime.
answered Dec 18 '18 at 21:26
John OmielanJohn Omielan
2,046210
$endgroup$
add a comment |
$begingroup$
I don't have a 50 reputation yet, so I am providing this as an answer. First, if there was a "general" way to find primes as you request, then this would provide a specific way to find prime numbers of basically any size, which as far as I know nobody has determined yet. Nonetheless, note that although any even value of $n$ will work, as the comments above stated, it will generally be easiest to find a prime if $n$ has many small, unique prime factors, especially if it's a primorial (i.e., the product of all primes up to a given prime, such as 2, 6, 30, 210, etc.). This is because $pn pm 1$ will then be relatively prime to all of those factors and, thus, it's more likely that one or both values are prime.
answered Dec 18 '18 at 21:26
John OmielanJohn Omielan
2,046210
$endgroup$
add a comment |
$begingroup$
I don't have a 50 reputation yet, so I am providing this as an answer. First, if there was a "general" way to find primes as you request, then this would provide a specific way to find prime numbers of basically any size, which as far as I know nobody has determined yet. Nonetheless, note that although any even value of $n$ will work, as the comments above stated, it will generally be easiest to find a prime if $n$ has many small, unique prime factors, especially if it's a primorial (i.e., the product of all primes up to a given prime, such as 2, 6, 30, 210, etc.). This is because $pn pm 1$ will then be relatively prime to all of those factors and, thus, it's more likely that one or both values are prime.
answered Dec 18 '18 at 21:26
John OmielanJohn Omielan
2,046210
$endgroup$
I don't have a 50 reputation yet, so I am providing this as an answer. First, if there was a "general" way to find primes as you request, then this would provide a specific way to find prime numbers of basically any size, which as far as I know nobody has determined yet. Nonetheless, note that although any even value of $n$ will work, as the comments above stated, it will generally be easiest to find a prime if $n$ has many small, unique prime factors, especially if it's a primorial (i.e., the product of all primes up to a given prime, such as 2, 6, 30, 210, etc.). This is because $pn pm 1$ will then be relatively prime to all of those factors and, thus, it's more likely that one or both values are prime.
answered Dec 18 '18 at 21:26
John OmielanJohn Omielan
2,046210
edited Dec 19 '18 at 3:26
answered Dec 18 '18 at 21:26
John OmielanJohn Omielan
2,046210
answered Dec 18 '18 at 21:26
John OmielanJohn Omielan
2,046210
answered Dec 18 '18 at 21:26
John OmielanJohn Omielan
2,046210
2,046210
add a comment |
add a comment |
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.
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%2f3034646%2ffinding-p-such-that-pn-pm-1-is-prime-for-a-fixed-n%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
$begingroup$
I don't understand your question. Right now, it sounds like you want to fix some $n$, and then find some prime $p$ such that either $pn+1$ or $pn-1$ is also prime. Then what? Are you asking if this is always possible? What is the actual question?
$endgroup$
– davidlowryduda♦
Dec 10 '18 at 23:37
$begingroup$
I assume OP is looking at a sort of generalization of the Sophie Germain primes. Choose a specific $n$, say $n=3$. Then for prime $p$, he wants to see which among $3p + 1$ are also prime, for example, which he seems to be doing via a script that checks primes $p$ up to $10^8$.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:39
$begingroup$
@davidlowryduda I'll try and edit the question to make it more clear. You are correct, I want to find some $p$ so that either $pn - 1$ or $pn + 1$ is prime. I'd like to be able to find the value in general for any $n$.
$endgroup$
– spyr03
Dec 10 '18 at 23:39
1
$begingroup$
Aside from that, I wonder if there's some sort of pattern in these $n$ that results in no such primes (at least in your investigations). Of course it could be possible that the primes that result are very large, but who knows. As one example of $n$ which won't work: It should be clear that $n$ which are odd won't work for odd primes $p$: $np$ will then be odd, and then $pm 1$ will be even, i.e. composite. So unless $2n pm 1$ is prime in those cases, $n$ odd never generates such a prime.
$endgroup$
– Eevee Trainer
Dec 10 '18 at 23:42
1
$begingroup$
@EeveeTrainer Oh, I completely missed that... That would explain why I haven't found an answer for $1683$. I guess we can assume $n$ is even then. :/
$endgroup$
– spyr03
Dec 10 '18 at 23:51