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


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?

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

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


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

  • $\begingroup$ What's the proof of this? $\endgroup$
    – Casteels
    Mar 12 '14 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
    Mar 12 '14 at 13:06
  • $\begingroup$ @Casteels: Right; I added the proof $\endgroup$
    – jpvee
    Mar 12 '14 at 13:22
  • $\begingroup$ Related: oeis.org/A076336 $\endgroup$
    – Casteels
    Mar 12 '14 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
    Mar 12 '14 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.