# Is $3^n - 2^n$ composite for all integers $n \geq 6$?

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?

-
$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
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
–  Byron Schmuland Jun 30 '12 at 17:07
Cameron Buie: Important remark! Byron Schmuland: Nice webpage! Thank you guys. –  Stavros Mekesis Jun 30 '12 at 17:13

$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?"}$$

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

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

-
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