281
$\begingroup$

I discovered this site which claims that "$7$ is the only prime followed by a cube". I find this statement rather surprising. Is this true? Where might I find a proof that shows this?

In my searching, I found this question, which is similar but the answers seem focused on squares next to cubes.

Any ideas?

$\endgroup$
6
  • 165
    $\begingroup$ Factor $x^3-1$. $\endgroup$
    – user940
    Feb 10, 2014 at 16:27
  • 15
    $\begingroup$ More generally, for each $k$, there is at most one prime that is followed by a $k$-th power: that number is $2^k-1$, but it is not always a prime: you need $k$ prime but not all primes $k$ give a prime $2^k-1$. See Mersenne prime. $\endgroup$
    – lhf
    Feb 10, 2014 at 16:34
  • 6
    $\begingroup$ Of course the above comments are related to the fact that the polynomial $x^k-1$ has $x=1$ as a root, and so $x-1$ divides that polynomial. $\endgroup$
    – Jeppe Stig Nielsen
    Feb 10, 2014 at 20:22
  • 12
    $\begingroup$ @barto I definitely did not expect this question to be received so positively. I also did not expect it to be a simple answer, but I'm not as deep into mathematics as the users here. One thing to always remember on SE sites is that your average users (at least the ones asking questions) are probably not an experts. While you may have great questions/answers exploring the mysteries of mathematics, the likelihood I understand it is low so I am unlikely to vote on those. Also, simple questions can lead to clever, simple answers. $\endgroup$
    – David Starkey
    Feb 10, 2014 at 20:55
  • 2
    $\begingroup$ A spin off is a proof that no even powers grater than 2 follow a prime number. For $n>2$ is no primes followed by even powers? $\endgroup$
    – kleineg
    Feb 17, 2014 at 17:23

5 Answers 5

Reset to default
289
$\begingroup$

This is certainly true. Suppose $n^3 - 1$ is prime, for some $n$. We get that $n^3-1 = (n-1)(n^2 + n + 1)$ and so we have that $n-1$ divides $n^3 - 1$. If $n-1>1$ then we're done, as we have a contradiction to $n^3 - 1$ being prime.

$\endgroup$
12
  • 6
    $\begingroup$ Wow, amazing!! Did you just make the proof yourself now, or has it been known to you already (or a similar type of proof)? $\endgroup$
    – Tomas
    Feb 10, 2014 at 18:26
  • 23
    $\begingroup$ @Tomas: this is a fairly standard sort of argument, the kind you would learn how to write down in any good course in elementary number theory. Many textbooks cover this and related topics. $\endgroup$
    – Qiaochu Yuan
    Feb 10, 2014 at 23:59
  • 21
    $\begingroup$ it puzzles me how this deserves a great answer badge comparing to answers like this math.stackexchange.com/questions/218131/… which needed some serious thinking. I am not saying the answer is not a good one, but it is almost utterly trivial. $\endgroup$
    – Lost1
    Feb 11, 2014 at 13:35
  • 28
    $\begingroup$ @Lost1: just there are more people able to undestand this one $\endgroup$
    – Sergey Grinev
    Feb 11, 2014 at 14:06
  • 28
    $\begingroup$ @Lost1 Congratulations, you've just observed that voting system of SE is screwed globally. (Still, it seems to quite well achieve to find local maxima). $\endgroup$
    – yo'
    Feb 11, 2014 at 14:51
258
$\begingroup$

$$ x^3 - 1 = \underbrace{(x-1)(x^2+x+1)}. $$ Being a product of two numbers, the expression over the $\underbrace{\text{underbrace}}$ is composite UNLESS $(x-1)=1$. That happens only if $x=2$, so $x^3=8$.

$\endgroup$
2
  • 10
    $\begingroup$ While both sides of the equation are always equal, x^3-1 cannot be a prime if it is equal to the multiplication of 2 numbers unless 1 of them is a 1. So x-1=1 when x is 2. While (x^2 + x + 1) = 1 when x = 0 or -1 they do not produce a positive integer when put into (x^3-1) and so cannot be prime either. $\endgroup$
    – BeowulfNode42
    Feb 11, 2014 at 15:55
  • 8
    $\begingroup$ This answer is easier to understand than the accepted one by @pgadey. I mean, what does "If n−1 > 1 We're done" mean? Shouldn't it be more like "n must equal 2 for n-1 to be 1, hence not a prime"? $\endgroup$
    – Nicolas Miari
    Feb 12, 2014 at 6:40
62
$\begingroup$

Key Idea $\ $ Composite polynomials take composite values (except for finitely many values)

Indeeed, suppose that $\ f(x)\color{#c00}{\ne 0}\ $ is a composite polynomial: $\, f(x) = g(x)h(x)\,$ with $\ g,\,h\color{#c00}{\ne \pm1}.\,$ Then $\, f(n) = g(n)h(n)\, $ is a composite integer if $\,g(n),\,h(n)\,\neq\, 0,\,\pm1.\,$ The possible exceptions to this are $ $ finite $ $ in number: $ $ when $\,n\,$ is a root of $\ g,\, h,\, g\pm1,\,$ or $\, h\pm1, \, $ all of which are $\color{#c00}{nonzero}$ polynomials, hence have finite sets of roots. $\ $ QED

Remark $\ $ For a specific composite polynomial $\,f = gh\,$ this yields a simple algorithm to enumerate its finitely many prime values: test if $\,f(n)\,$ is prime as $\,n\,$ ranges over the roots of $\,g\pm1\,$ or $\,h\pm1.\,$ Applying this to $\, f = x^3-1 = (x-1)(x^2\!+x+1)\,$ quickly yields the sought result.

Hence the method used in the other answers is a special case of a method that works generally. Furthermore, this is an instance of a general philosophy relating the factorizations of polynomials to the factorizations of their values (see said answer for much more on this viewpoint).

$\endgroup$
5
  • 6
    $\begingroup$ I did not downvote, but, imo, someone with 108k reputation should not post an answer to a clearly overrated question 2 hours after 3 answer have not emerged, and your proof is an overkill. Given that the OP has asked the question, it is pretty clear your answer is unlikely to be accessible for his level of mathematics. $\endgroup$
    – Lost1
    Feb 11, 2014 at 13:38
  • 63
    $\begingroup$ @Lost1 Answers teach many readers besides the OP. My sole motivation here is to teach math (not to play the SE rep game). This is a perfect teaching opportunity - a simple problem whose key ideas lead to many interested related results, including deep open problems (follow the links). This is one of the tantalizing aspects of number theory - that simple looking problems often encode deep, interesting math. Things like this are what sparked me to study number theory. I strive to pass along the mathematical torch, hoping that it will similarly spark others, for there lies much beauty. $\endgroup$
    – Bill Dubuque
    Feb 11, 2014 at 14:56
  • 3
    $\begingroup$ I agree with you, Bill Dubuque. Having read other answers of you I've noticed that you quite often want to show an underlying, more global concept. I appreciate this style of answering (some do not apparently, which I can understand), but perhaps this time you are a little exagerating. $\endgroup$
    – Bart Michels
    Feb 11, 2014 at 20:24
  • 8
    $\begingroup$ @barto I'm not exaggerating. The study of this and related matters leads quickly to interesting and challenging unsolved problems in number theory, such as nonlinear analogs of Dirichlet's theorem on primes in progressions (e.g. Bunyakovsky's conjecture). Any methods that solve these or related problems would probably lead to major breakthroughs. See Chapter 6 of Ribenboim's The New Book of Prime Number Records for a very readable discussion on this. $\endgroup$
    – Bill Dubuque
    Feb 11, 2014 at 20:48
  • 2
    $\begingroup$ @BillDubuque I suppose you're right, I think you're talking about subjects I can't yet imagine nor understand, so I bet I can not yet realize the importance of what's in your answer. $\endgroup$
    – Bart Michels
    Feb 11, 2014 at 21:18
40
$\begingroup$

You want to know when $x^3-1$ is prime. This expression can be written as $(x-1)(x^2+x+1)$, So it is always divisible by $(x-1)$. If a prime is divided by $(x-1)$, so $x-1=1$ or $x=2$ and $x^3-1=7$.

$\endgroup$
16
$\begingroup$

Wouldn't $-2$ also be a prime followed by $-1$ which is a cube of $-1$. As $x^2 + x +1$ will also equal one for $x=-2$.

$\endgroup$
11
  • 18
    $\begingroup$ Negative integers can not be prime. $\endgroup$
    – Zafer Cesur
    Feb 10, 2014 at 19:46
  • 14
    $\begingroup$ @Zafer: It is very common to take the point of view that $-p$ is prime whenever $p$ is. $\endgroup$
    – MJD
    Feb 10, 2014 at 20:05
  • 4
    $\begingroup$ You could make the same argument for x=0 but to my understanding primes are positive integers larger than 1. $\endgroup$
    – David Starkey
    Feb 10, 2014 at 20:17
  • 8
    $\begingroup$ While in ring theory the additive inverses of primes are also considered to be prime, the context of the question and the linked site are most likely only referring to positive natural numbers. $\endgroup$
    – rschwieb
    Feb 10, 2014 at 20:20
  • 3
    $\begingroup$ This interpretation depends on your definition of "followed by." I take it to mean "moving away from zero," not "increasing toward positive infinity." $\endgroup$
    – Greg
    Feb 10, 2014 at 23:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .