# Are there infinitely many primes of the form $k\cdot 2^n +1$?

Let's observe following matrix with an infinite number of elements : Elements of the main diagonal are of the form $n\cdot2^n+1$ . These numbers are known as Cullen numbers . It is an open question whether there is an infinite number of Cullen primes. In fact Cullen prime is special case of prime number of the $k\cdot 2^n +1$ form.

So, maybe easier question is : Are there infinitely many primes of the form $k\cdot 2^n +1$ ?

• Every prime $p$ that is congruent to $1$ modulo $4$ is of the form $4m+1$ for some $m$. Write $m=2^ak$ with $k$ odd, then $p=k2^{a+2}+1$. If $n$ is supposed to be fixed, then just look for the primes of this form greater than an appropriate bound. Or did you mean to both fix $n$ and require $k$ odd? – Arturo Magidin Nov 6 '11 at 5:58
• So the answer is "yes", and in fact, the OEIS has sequences for the least odd $k$ for any given $n$ here – Arturo Magidin Nov 6 '11 at 6:07
• @Arturo,I am interested in a formal proof that there are infinitely many primes of the form $k \cdot 2^n+1$ if one exists,no special constraints. – Peđa Terzić Nov 6 '11 at 6:08
• @Arturo,If it is so what we may conclude about number of Cullen primes ? – Peđa Terzić Nov 6 '11 at 6:12
• marty cohen's argument gives a formal proof. Take the arithmetic progression $a+bm$ with $m\in\mathbb{N}$, $a=2^n+1$, $b=2^n$. Since $\gcd(a,b)=1$, then the progression has infinitely many primes. And $a+bm = (m+1)2^n+1$. This shows that for each $n$ there are infinitely many primes of the given form. – Arturo Magidin Nov 6 '11 at 6:13

## 3 Answers

The first row of the OP's matrix is 3,5,7,..., and so obviously contains every prime except 2. More generally, Dirichlet's theorem implies that each row contains an infinite number of primes (as pointed out by marty cohen).

A Sierpinski number is a odd positive integer $k$ such that $k \cdot 2^n +1$ is composite for all $n \geq 1$. The smallest known Sierpinski number is $78557$ [the Seventeen or Bust team are trying to (computationally) prove it is the smallest]. Sierpinski showed that there are an infinite number of Sierpinski numbers, so there are an infinite number of all-composite columns in the OP's matrix (which extends zyx's answer).

Numbers of the form $k \cdot 2^n+1$ with $k<2^n$ are (sometimes) referred to as Proth numbers. Proth's Theorem gives a necessary and sufficient condition for the primality of a Proth number. Yves Gallot proth.exe is an available implementation of Proth's Theorem. Many of the largest known primes are Proth primes.

Related are numbers of the form $k \cdot 2^n-1$, for which we can detect primality via the efficient Lucas-Lehmer-Riesel test, implemented by Jean Penné's LLR. Also, there's Mersenne numbers, for which there's the giant GIMPS project searching for large Mersenne primes.

Here's a simple-minded answer from simple-minded (at least in this group) me: Yes.

Use Dirichlet's theorem on primes in an arithmetic progression, for any $n$, the arithmetic progression $k 2^n+1$, $k = 1, 2, ...$ contains an infinite number of primes.

• And if you want $k$ odd, start with $a=2^n+1$, $b=2\times 2^{n}$, and look at $a+bm$. – Arturo Magidin Nov 6 '11 at 6:06

There are values of $k$ for which all terms of the sequence $k.2^n + 1$ are composite. The proof uses covering congruences, starting from Euler's factorization of the fifth Fermat number; a finite set of primes is constructed and a set of congruence conditions that cover all $n$, and each condition forces divisibility by one of the primes.

There is no known value of $k$ for which it is proven that infinitely many primes exist in the sequence $k2^n + 1$.