Finding $p$ such that $pn \pm 1$ is prime for a fixed $n$

Question

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

Answer 1

Note 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, 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 note have any of those smaller primes as factors and, thus, it's more likely that one or both values are prime.

Answer 2

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

[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