3
$\begingroup$

Let's observe following matrix with an infinite number of elements :

enter image description here

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

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – Arturo Magidin
    Commented Nov 6, 2011 at 5:58
  • 1
    $\begingroup$ So the answer is "yes", and in fact, the OEIS has sequences for the least odd $k$ for any given $n$ here $\endgroup$
    – Arturo Magidin
    Commented Nov 6, 2011 at 6:07
  • $\begingroup$ @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. $\endgroup$
    – Pedja
    Commented Nov 6, 2011 at 6:08
  • 2
    $\begingroup$ 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. $\endgroup$
    – Arturo Magidin
    Commented Nov 6, 2011 at 6:13
  • 1
    $\begingroup$ @Arturo,Ok,I understand how to write formal proof.I think that one can make analogy : "If we know that there is an infinite number of quadrilaterals can we prove that there is infinite number of rectangles " $\endgroup$
    – Pedja
    Commented Nov 6, 2011 at 6:24

3 Answers 3

Reset to default
9
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

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

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .