10
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ $k=8$ seems to work. $\endgroup$ Commented Mar 12, 2014 at 0:45
  • $\begingroup$ Sorry, I of course meant $k$ coprime to 2. $\endgroup$
    – ant11
    Commented Mar 12, 2014 at 0:46
  • 1
    $\begingroup$ Oh, bummer! $k=773$ looked promising, but it seems that $2^{955}+773$ is prime. :( $\endgroup$
    – jpvee
    Commented Mar 12, 2014 at 12:16

1 Answer 1

16
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ What's the proof of this? $\endgroup$
    – Casteels
    Commented Mar 12, 2014 at 12:46
  • $\begingroup$ 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}$. $\endgroup$
    – Casteels
    Commented Mar 12, 2014 at 13:06
  • $\begingroup$ @Casteels: Right; I added the proof $\endgroup$
    – jpvee
    Commented Mar 12, 2014 at 13:22
  • $\begingroup$ Related: oeis.org/A076336 $\endgroup$
    – Casteels
    Commented Mar 12, 2014 at 15:19
  • 2
    $\begingroup$ 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)? $\endgroup$
    – ant11
    Commented Mar 12, 2014 at 16:21

You must log in to answer this question.

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