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.

I made a conjecture about the values of n for which $3^n - 2^n$ is not prime, but I didn't succeed in proving the conjecture. My conjecture is the following: "Suppose n is an integer greater than or equal to 6. Then $3^n - 2^n$ is not prime". I tried to prove that by induction, but I got stuck. Any ideas?

share|improve this question
11  
$3^{17} - 2^{17} = 129009091$ is prime. –  Arthur Fischer Jun 30 '12 at 16:58
    
Thanks for your counterexample! :-) –  Stavros Mekesis Jun 30 '12 at 17:02
6  
Be wary of attempting to prove by induction that numbers of a certain form are always prime. The irregular distribution of primes make such a venture unlikely to succeed. –  Cameron Buie Jun 30 '12 at 17:04
3  
See oeis.org/A057468 –  Byron Schmuland Jun 30 '12 at 17:07
1  
Cameron Buie: Important remark! Byron Schmuland: Nice webpage! Thank you guys. –  Stavros Mekesis Jun 30 '12 at 17:13

3 Answers 3

up vote 8 down vote accepted

$n=17$ gives us $3^n-2^n = 129009091$, which is a prime number. Below is a list for $n \leq 100000$. $$ \begin{array}{|c|c|} \hline n& (3^n-2^n)\\ \hline 2 & 5\\ 3 & 19\\ 5 & 211\\ 17 & 129009091\\ 29 & 68629840493971\\ 31 & 617671248800299\\ 53 & 19383245658672820642055731\\ 59 & 14130386091162273752461387579\\ 101 & 1546132562196033990574082188840405015112916155251\\ 277 & \text{A $133$ digit prime number}\\ 647 & \text{A $309$ digit prime number}\\ 1061 & \text{A $507$ digit prime number}\\ 2381 & \text{A $1137$ digit prime number}\\ 2833 & \text{A $1352$ digit prime number}\\ 3613 & \text{A $1724$ digit prime number}\\ 3853 & \text{A $1839$ digit prime number}\\ 3929 & \text{A $1875$ digit prime number}\\ 5297 & \text{A $2528$ digit prime number}\\ 7417 & \text{A $3539$ digit prime number}\\ 90217 & \text{A $43045$ digit prime number}\\ \hline \end{array}$$ It is clear that if $3^n - 2^n$ is a prime, then $n$ has to be a prime but the converse is not true. In general, questions like these are likely to be hard.

For instance, replacing the $2$ by $1$ and $3$ by $2$ in your question, we get the Mersenne prime i.e. a prime of the form $2^n-1$. For instance, $31$ is a Mersenne prime, since $31 = 2^5-1$. Similarly, $127 = 2^7-1$ is also a Mersenne prime.

The Mersenne prime conjecture asks the following question

$$\text{"Are there infinitely many Mersenne primes?"}$$

share|improve this answer
    
@Mavris: Thank you! Do we know whether or not there are infinitely many primes of that form? –  Stavros Mekesis Jun 30 '12 at 17:23
1  
@Stavros It is clear that if $3^n - 2^n$ is a prime, then $n$ has to be a prime but the converse is not true. In general, questions like these are likely to be hard. For instance, replacing the $2$ by $1$ and $3$ by $2$ in your question, we get the Mersenne prime i.e. a prime of the form $2^n-1$. For instance, $31$ is a Mersenne prime, since $31 = 2^5-1$. Similarly, $127 = 2^7-1$ is also a Mersenne prime. The Mersenne prime conjecture (which is unsolved as of today) asks the following question $$\text{"Are there infinitely many Mersenne primes?"}$$ –  user17762 Jun 30 '12 at 17:24
    
Why must n be prime if 3^n-2^n is prime ? –  user1708 Jun 30 '12 at 18:25
2  
@barney If $n$ is not a prime, then $n = ab$, where $1 < a,b <n$. This means $$3^n - 2^n = 3^{ab} - 2^{ab} = (3^a)^b - (2^a)^b$$ Recall that $(x-y)$ divides $x^n - y^n$. Hence, we have that $(3^a - 2^a)$ divides $3^n - 2^n$. Further since $1< a < n$, we have that $3^a - 2^a$ is a proper divisor of $3^n - 2^n$. Hence, if $n$ is composite, so is $3^n - 2^n$. Equivalently, to put it he other way, if $3^n-2^n$ is prime, then so is $n$. –  user17762 Jun 30 '12 at 18:29
    
@Stavros These questions tend to be extremely hard. I believe it's also unknown that $2^p - 1$ is composite for infinitely many primes $p$, even though this is by far the more common occurrence (empirically). Presumably this is also true for $3^p-2^p$. –  Erick Wong Jun 30 '12 at 20:15

Nope, $3^{31} - 2^{31} = 617671248800299$ which as everyone knows is prime.

share|improve this answer
    
Thanks! Can we prove that there are infinitely many prime of that form? –  Stavros Mekesis Jun 30 '12 at 17:09
    
Heeeeeeeeeee!!!! –  ncmathsadist Jul 1 '12 at 1:52

Unfortunately, $3^{17}-2^{17}$ is prime.

It is clear that for primality the exponent $n$ must be prime. I would expect that no one knows whether there are infinitely many such primes. (This is based on the so far unsuccessful attempts to prove that there are infinitely many primes of the shape $2^n-1$.)

share|improve this answer
    
Thanks! Are there infinitely many primes of the form $3^n - 2^n$? –  Stavros Mekesis Jun 30 '12 at 17:05
    
I suspect that this question is in the same sort of category as the Mersenne prime conjecture - possibly true, but very hard to prove (or disprove), and almost certainly no approachable by induction. –  Old John Jun 30 '12 at 17:22
    
@Stavros: I do not know. Probably nobody does, if we consider the history of similar problems, like the Mersenne prime problem. –  André Nicolas Jun 30 '12 at 17:23

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.