Can we find $n$ such that $3061\cdot2^n +1$ is prime

elementary-number-theorynumber theory

Let $p=3061$. Can we find an integer $n$ such that $2^n p+1$ is prime? If there is no such $n$, how can we prove it? Or does such $n$ always exist for prime $p$?

(More generally, instead of $p=3061$, you can try e.g. $p=5297,5897,7013,8423,\ldots$ — there are quite a few primes $p$ for which brute force does not seem to work.)

Motivation: questions like these arise naturally while reading the paper
On the density of odd integers of the form $(p − 1)2^{-n}$ and related questions
by Paul Erdös and Andrew Odlyzko.

Best Answer

These are Proth numbers so you can apply Proth's theorem for efficient primality testing (see also Are there primes $p=47\cdot 2^n+1$?.). This way, we can verify that the pseudoprime posted by @DmitryEzhov in comments is indeed a prime by choosing $a=3$, $N=3061\cdot 2^{33288}+1$, because $$ a^{\frac{N-1}{2}} \equiv -1 \pmod{N}. $$ (e.g. a := 3: p := 3061*2^33288+1: is((Power(a, (p-1)/2) mod p) = p-1) in Maple).

Also Effective Primality Test for $p2^n+1$, $p$ prime, $n>1$ could be of interest. It especially mentions:

Sierpinski numbers of the second kind are integers $k$ such that $k2^n + 1$ is not prime for all positive integers $n$.

So in your case, if the Sierpinski number $k=p$ happens to be a prime, you will not find $n$ such that $p2^n+1$ is a prime. There are infinitely many such numbers, the $k=271129$ is conjectured to be the smallest (see Prime Sierpinski problem). See Alex's answer for more examples.

Even more reading The Sierpiński Problem: Definition and Status.

Related Question