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

Question

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.

Answer 1

Not a complete solution but some observations. Let $a_n=2^np+1$.

I. If $n$ is odd then $3\,|\,a_n$.

Pf: Indeed $3061\equiv 1 \pmod 3$ so $a_n\equiv 2^n+1\pmod 3$ and the claim follows.

II. If $n\equiv 2 \pmod 4$ then $5\,|\,a_n$

Pf: Indeed, $3061\equiv 1 \pmod 5$ so $a_n\equiv 2^n+1\pmod 5$ and the claim follows.

So you only need to worry about $n\equiv 0 \pmod 4$. For those there does not appear to be a simple congruence. Indeed, for $n\in \{1,\cdots 10\}$ the least prime which divides $a_{4n}$ is, respectively, $$\{17,19,17,797, 17,821,17,31,17,59\cdots\}$$

From which we are led to conjecture that $n\equiv 4 \mod 8\implies 17\,|\,a_n$, which is easily proven (since $3061\equiv 1\pmod {17}$ and $2^4\equiv -1 \pmod {17}$).

That just leaves $n\equiv 0\pmod 8$ to study.

Answer 2

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.

Answer 3

Carrying forward the observations of @lulu:

If $n = 0$ (mod 8), then $19| a_n$ for $n=8, 80, 152, 224,...$ i.e. for $8$ and every ninth multiple of $8$.

For since $2^8=9$ (mod $19$), and $3061=2$ (mod $19$), then $2^8\cdot3061+1=9\cdot2+1=0$ (mod 19). Further, since $2^{72}=1$ (mod $19$), then $19|a_n$ for $n=8, 80, 152, 224,...$.

In the same way we find that $31|a_n$ for $n=32, 72, 112, 152,...$, i.e. for every fifth multiple of $8$ beginning with $32$.

$37|a_n$ for $n=48, 120, 192, 264,...$, or every ninth multiple of $8$ from $48$.

$43|a_n$ for $n=32, 88, 144, 200,...$,i.e. for every seventh multiple of $8$ beginning with $32$.

Once more, $53|a_n$ for $n=80, 184, 288, 392...$, or every thirteenth multiple of $8$ from $80$.

Thus, even allowing for some overlap, it seems that with just these five primes we sieve out$$\frac19+\frac15+\frac19+\frac17+\frac{1}{13}>\frac12$$of $a_n$ as necessarily composite.

If we did not have an accepted answer to the question, this could have at least further narrowed the search.

Answer 4

Here is a more elaborate answer to the question: does such $n$ always exist for prime $k=p$? (This complements the answers given earlier.)

Sierpinski number is an odd integer $k$ such that $k\cdot2^n+1$ is composite for all $n\in{\mathbb N}$. Sierpinski's paper Sur un probleme concernant les nombres $k\cdot2^n+1$ (1960) proved that there are infinitely many $k$ with this property. Namely, he proved that if $k$ satisfies two congruences: $$ k \equiv 1 \ ({\rm mod}\ q_1), \ \quad q_1=(2^{32}-1)\cdot641=2753074036095, \tag{1} $$ $$ k \equiv -1 \ ({\rm mod}\ q_2) \quad q_2=(2^{32}+1)/641\,=\,6700417, \qquad\quad \tag{2} $$ then $k$ is a Sierpinski number. We will now prove the following simple corollary of Sierpinski's result.

Corollary: Infinitely many primes are Sierpinski numbers.

Proof. We will show that infinitely many primes satisfy Sierpinski's congruences $(1)$, $(2)$. Indeed, choose $$ a=15511380746462593381, \qquad q=q_1 q_2=18446744073709551615. $$ Then all terms $k_m$ of the arithmetic progression $$ k_m=a+mq,\quad m\in{\mathbb N}, \tag{3} $$ satisfy both congruences $(1)$ and $(2)$. So all $k_m$ are Sierpinski numbers.

But note that $\gcd(a,q)=1$. Therefore, by Dirichlet's theorem on arithmetic progressions, there are infinitely many primes in the progression $a+mq \ \ (3). \ \ $ Q.E.D.

Here are the first five primes in progression $(3)$: $$52404868893881696611$$ $$273765797778396315991$$ $$347552774073234522451$$ $$827168119989682864441$$ $$1306783465906131206431$$