Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
The title is much better now! –  lhf Oct 7 '11 at 21:09
add comment

3 Answers 3

up vote 23 down vote accepted

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.

share|improve this answer
    
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. –  Zev Chonoles Oct 7 '11 at 19:35
    
@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. –  Charles Oct 7 '11 at 19:44
1  
AFAIK = "As far as I know" –  user02138 Oct 7 '11 at 21:52
    
Is this technique also applicable here? –  draks ... Jun 20 '12 at 18:41
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. –  Charles Jun 20 '12 at 23:41
add comment

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.

share|improve this answer
1  
+1. This was the same method I used to solve the (edited) question. –  Charles Oct 7 '11 at 19:49
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 :-) –  Jyrki Lahtonen Oct 7 '11 at 20:26
    
Is this technique also applicable here? –  draks ... Jun 20 '12 at 18:42
add comment

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

share|improve this answer
    
+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? –  Jyrki Lahtonen Oct 7 '11 at 20:44
    
@Jyrki, yes, it affects only the constant. –  zyx Oct 7 '11 at 20:51
    
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$. –  Jyrki Lahtonen Oct 8 '11 at 5:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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