12
$\begingroup$

How to prove that $2^n+3$ and $2^n+5$ are both prime for only finitely many integers $n$?

And how to prove that there are infinitely many primes of the form $2^n+3$ and $2^m+5$

3 Answers 3

24

What makes you think that there are only finitely many? A057732 shows a large number of primes of the form $2^n+3$, and likewise A059242 for $2^n+5.$

Generally the way that such sequences are shown to have only finitely many primes is to find a covering set, but there's no obvious one for either.


To answer the edited question: There are only finitely many twin primes of the form $(2^n+3,2^n+5)$ because there is a covering set: at least one of the numbers is divisible by a member of $\{3,5,7,13\}$ (work mod 12). But proving that there are infinitely many primes of either form is beyond current technology AFAIK.

  • 0
    The OP has edited the question to include whether there are finitely many times *both* $2^n+3$ and $2^n+5$ are prime. It seems more likely that there are only finitely many of these, although (I would guess) still unlikely that we would be able to prove it.2011-10-07
  • 0
    @ZevChonoles: Thanks, I edited my answer to address the new question. Actually it can be proven that there are only finitely many twin primes of this form, though proving that there are infinitely many primes in either form is well beyond what can currently be proven I think.2011-10-07
  • 1
    AFAIK = "As far as I know"2011-10-07
  • 0
    Is this technique also applicable [here](http://math.stackexchange.com/q/148895/19341)?2012-06-20
  • 1
    @draks: Probably not. But if it were applicable in some case, that would be 'trivial' compared to the others. Resolving those questions will probably be very hard. For example, by probability you'd expect infinitely many Mersenne primes, but no one knows how to prove it. The 'chance' that they appear as part of a twin prime pair is small enough that it should happen only finitely often, but this too is more than can be proved.2012-06-20
18

Settling the twin prime part of the question seems to go as follows:

1) If $2\mid n$, then $3\mid 2^n+5$, so it suffices to study odd values of $n$.

2) If $n\equiv 1\pmod 4$, then $5\mid 2^n+3$, so it suffices to study the case $n\equiv 3\pmod 4$.

3) If $n\equiv 1\pmod 3$, then $7\mid 2^n+5$. If $n\equiv 2\pmod 3$, then $7\mid 2^n+3$, so for there to be infinitely many twin primes of this form we must have $3\mid n$.

Combinining items 2 and 3 above, we see that it suffices to exclude the possibility of infinitely many twin primes of this form, when $n\equiv 3\pmod {12}$. But...

4) If $n\equiv 3\pmod {12}$, then $13\mid 2^n+5$.

Looks like $(5,7)$ and $(11,13)$ are all.

  • 1
    +1. This was the same method I used to solve the (edited) question.2011-10-07
  • 3
    Folks, thank you for your support, but Charles solved this problem a couple of minutes earlier. Study the edit history of his answer for a proof :-)2011-10-07
  • 0
    Is this technique also applicable [here](http://math.stackexchange.com/q/148895/19341)?2012-06-20
4

And how to prove that there are infinitely many primes of the form $2^n+3$

First prove that there are infinitely Mersenne primes, then...

This is something that can be predicted, not proved, in the current state of number theory.

The "probability" of prime numbers near $2^n$ is close to $1/\log (2^n) = \frac{1}{n \log 2}$ and the "expected number" of primes of the form $2^m+3$ in $[1,n]$ is $O(\log \log n)$.

  • 0
    +1 Interesting. But is it possible to factor in facts of the form (see the other answers): $2^n+3$ is slightly more probable to be divisible by $5$ (1 out of 4) or by $7$ (1 out of 3) than the usual "random integer near a power of two"? Can it be shown that such considerations only affect the constant of $O(\log\log n)$? Ok, in this case this is clearly asking too much, but are there other questions, where such slight bias away from being prime can be factore in?2011-10-07
  • 0
    @Jyrki, yes, it affects only the constant.2011-10-07
  • 0
    Is it easy to see that? I didn't mean to only consider divisibility by $5$ or $7$. For any prime $p$, if $2$ is a primitive root modulo $p$, then $2^n+3$ is divisible by $p$ with 'probability' $1/(p-1)$ (as opposed $1/p$ that we would have with a 'random' integer). If $2$ is not a primitive root modulo $p$, then this probability is either zero or $1/d$ according to whether $-3$ is in the group generated by $2$. Here $d\mid p-1$ is the order of $2$ modulo $p$.2011-10-08