1
$\begingroup$

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?

  • 11
    $3^{17} - 2^{17} = 129009091$ is prime.2012-06-30
  • 0
    Thanks for your counterexample! :-)2012-06-30
  • 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.2012-06-30
  • 3
    See http://oeis.org/A0574682012-06-30
  • 1
    Cameron Buie: Important remark! Byron Schmuland: Nice webpage! Thank you guys.2012-06-30

3 Answers 3

5

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

  • 0
    Thanks! Are there infinitely many primes of the form $3^n - 2^n$?2012-06-30
  • 0
    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.2012-06-30
  • 0
    @Stavros: I do not know. Probably nobody does, if we consider the history of similar problems, like the Mersenne prime problem.2012-06-30
8

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

  • 0
    Thanks! Can we prove that there are infinitely many prime of that form?2012-06-30
  • 0
    Heeeeeeeeeee!!!!2012-07-01
7

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

  • 0
    @Mavris: Thank you! Do we know whether or not there are infinitely many primes of that form?2012-06-30
  • 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?"}$$2012-06-30
  • 0
    Why must n be prime if 3^n-2^n is prime ?2012-06-30
  • 2
    @barney If $n$ is not a prime, then $n = ab$, where $1 < a,b . 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$.2012-06-30
  • 0
    @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$.2012-06-30