# Does there exist some $k$ such that $2^n+k$ is never prime?

Does there exist some odd positive integer $k$ such that, for all integers $n>0$, $2^n+k$ is never prime?

Extension:

If yes, for any $a$, does there always exist some $b$ such that $a^n+b$ is never prime?

If no, do there exist some coprime positive integers $a,b>1$, such that $a^n+b$ is never prime?

• $k=8$ seems to work. Mar 12 '14 at 0:45
• Sorry, I of course meant $k$ coprime to 2. Mar 12 '14 at 0:46
• Oh, bummer! $k=773$ looked promising, but it seems that $2^{955}+773$ is prime. :( Mar 12 '14 at 12:16

$k=78557$ does the job for the first problem.

Proof:

Let $k>0$, $n := 78557+2^k$.

Case 1: $k\equiv 0\pmod 2$. Then $3|n$.
Case 2: $k\equiv 3\pmod 4$. Then $5|n$.
Case 3: $k\equiv 1\pmod{12}$. Then $13|n$.
Case 4: $k\equiv 5\pmod{12}$. Then $7|n$.
Case 5: $k\equiv 9\pmod{36}$. Then $37|n$.
Case 6: $k\equiv 21\pmod{36}$. Then $19|n$.
Case 7: $k\equiv 33\pmod{36}$. Then $73|n$.

Since the distinction covers all possible cases, $n$ is always composite.

Regarding the second part: I believe that an existence of a $b$ such that $a^n+b$ is composite for all $n>0$ is very likely as expessions such as $a^{36}-1$ tend to have "enough" different prime factors for constructing a "covering set" as the set $\{3,5,7,13,19,37,73\}$ above. Then, using the Chinese Remainder Theorem, you should be able to construct a suitable $b$.

• What's the proof of this? Mar 12 '14 at 12:46
• Oh I see this is an old result of Selfridge, but I'm having trouble finding the paper (it may be unpublished). I guess the idea is to show that for this $k$, $2^n+k$ is divisible by one of $\{3,5,7,13,19,37,73\}$ where the divisor depends on the value of $n\pmod{36}$. Mar 12 '14 at 13:06
• @Casteels: Right; I added the proof Mar 12 '14 at 13:22
• Related: oeis.org/A076336 Mar 12 '14 at 15:19
• This might be a trivial question, but how do we know that the primality of $78557+2^k$ and $78557\times 2^k+1$ are equivalent (in relation to the posts about Sierpinski numbers)? Mar 12 '14 at 16:21