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?"

  • $\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

To be precise, there is no "general method," to know which $p$ will yield $pn\pm 1$ prime for any given $n$, however there are many ways to check the primality of each individual $pn\pm 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$; $pn\pm 1$ is prime if and only if

$(x+a)^{pn\pm 1}\equiv (x^{pn\pm 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 -1\mod 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 -1\mod np+1$ and $a^{\frac{n}{2}}\not\equiv -1\mod 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




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.

  • $\begingroup$ @BillDubuque I've done as you've requested. Note I don't mind doing it, but is there any particular reason you did not do this yourself? $\endgroup$ – John Omielan Apr 10 at 23:10

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.