The Wikipedia (https://en.wikipedia.org/wiki/1000_(number)#1300_to_1399) mentions that 1331 is the only cube of the form $x^2 + x − 1$, for $x = 36$. What is the proof?

8$\begingroup$ let me swap your variables and try to solve y^2 + y = x^3 + 1. That looks like an elliptic curve, and in fact it's this one: lmfdb.org/EllipticCurve/Q/225/c/2 In fact what you write is not quite true, since 0^2 + 0  1 = (1)^3, and 1^2 + 1  1 = 1^3. But the solution you've got is sort of the interesting one. $\endgroup$– pupshawCommented Jun 9, 2021 at 18:42

11$\begingroup$ @NoahSchweber Why? There is nontrivial mathematics here, and the OP knows her mathematics $\endgroup$– Yemon ChoiCommented Jun 9, 2021 at 20:05

5$\begingroup$ To correct Thomas Browning's comment above, the curve is actually rank $1$, so there are infinitely many rational solutions, stating $(61/25, 434/125)$, $(71/144, 973/1728)$, $(779/1849, 125945/79507)$ ... $\endgroup$– David E SpeyerCommented Jun 10, 2021 at 0:46

3$\begingroup$ According to LMFDB, $y^2+y=x^3+1$ has integral solutions as follows. $ (x,y)=(1, 0) , (1, 1) , (1, 1) , (1, 2) , (11, 36) , (11, 37). $ Hence only positive integral solutions are $(x,y)=(1, 1),(11, 36).$ Using generator $(x,y)=(1,1)$, we can get positive rational solutions such as $(61/25, 434/125),(408241/45796, 256170307/9800344),(479399/2739025, 2812459393/4533086375)$. $\endgroup$– TomitaCommented Jun 10, 2021 at 3:47

3$\begingroup$ ... The Dipohantine equation $u^2v^3=k$ is known as *Mordell's equation". It has been extensively studied; in particular, Mordell has shown that for any integer $k$ the equation has only a finite number of solutions. For some values of $k$, Mordell's equation can be solved using an elementary argument, not appealing to elliptic curves. I do not know whether the case $k=80$ admits an elementary solution, just search the web / arXiv. $\endgroup$– SevaCommented Jun 11, 2021 at 8:14
2 Answers
Here is the more elementary way that one would have solved this before LLL. I will still use the computer for some calculations, but technically one could do all this by hand. Worse, I won't even do all of the steps, but I hope the part I show explains the method, for those that may be interested. Maybe someone wants to complete it or finds a shorter way.
First, setting $K=\mathbb{Q}(\theta)$ with $\theta^2+\theta1$, a.k.a the Golden ratio, we will rewrite our equation as $$N_{K/\mathbb{Q}}(y\theta) = x^3$$ to be solved in $X$ and $y$ in $\mathbb{Z}$. The field $K$ has class number 1 and the units are generated by $\theta$. From this, using a little argument about the $\sqrt{5}$adic valuation, one can show that, there must be a $i\in \{0,1,2\}$ such that $$y\theta = \theta^i\cdot \alpha^3$$ for some $\alpha\in\mathbb{Z}[\theta]$, the ring of integers of $K$. Write $\alpha = a+b\,\theta$ for $a,b\in\mathbb{Z}$ and split into the three cases according to $i$.
Case $i=0$ : Spanning out $\alpha^3$ and equating the coefficients in front of $\theta$, we get $$\begin{align*} y &= a^3+3ab^2b^3 \\ 1&=b\cdot(3a^23ab+2b^2)\end{align*}$$ Now the second line tells us that $b=\pm 1$, but neither of the choices allows us to find $a$ as an integer, so that case does not occur.
Case $i=1$ : This time the equations are $$\begin{align*} y &= 3a^2b3ab^2+2b^3\\1 &=a^33a^2b+6ab^23b^3\end{align*}$$ One can note here aside that the second line is a model of the curve $3$isogenous to the original curve over $\mathbb{Q}$. This second (Thue) equation, we rewrite as $$1 = N_{L/\mathbb{Q}}(ab\xi)$$ where $L=\mathbb{Q}(\xi)$ and $\xi^33\xi^2+6\xi3=0$. This $L$ has also trivial class number and the units are generated by $1\xi$ of norm $1$. We are now looking for units of norm $1$ in $L$ with no $\xi^2$ term. Once more we split into three cases $j\in\{0,1,2\}$. We want to solve $$a+b\xi =  (1\xi)^j\cdot(1\xi)^{3k} = (1\xi)^j\cdot(2+3\xi)^k.$$
Subcase $j=0$ : We may rewrite it as $$ab\xi =  (1+3(\xi1))^k = \bigl(1+3(\xi1)k+9(\xi1)^2k(k1)/2 + 27\cdots \bigr)$$ and consider this as a power series in $k$ over $\mathbb{Q}_3(\xi)$, which is a totally ramified extension of $\mathbb{Q}_3$. We can compare the power series coefficient in front of $\xi^2$, to get an equation of the form $$0=9 k (k1)\cdot \bigl(1/2 9/24 (k2)(k3)+\cdots\bigr).$$ By Strassmann's theorem, the power series has at most two solutions in $\mathbb{Q}_3$. But it is easy to spot that there are two such solutions, namely $(a=1,b=0,k=0)$ and $(a=2,b=3,k=1)$. These correspond to $(x,y)=(1,0)$ and $(11,36)$ repsectively.
Subcase $j=1$ : leads to a single solution $ab\xi=1+\xi$ which corresponds to $(x,y)=(1,2)$.
Subcase $j=2$ : produces a unit power series and has therefore no solutions.
Case $i=2$ : I believe one just gets the $P$ for all the $P$ found in the case $i=1$. But I admit that I have not checked.
Finally, I should say that for questions on integral points on elliptic curve I often turn to Smart's "The algorithmic Resolution of Diophantine Equations" that explains things well. Like the $3$adic method used in the subcases in chapter III.

2$\begingroup$ Regarding the $i=2$ case: Given a solution to $y\theta = \theta^2 \alpha^3$, rewrite it as $y  \theta = \theta^{1} \beta^3$ for $\beta = \theta \alpha$. Then apply the Galois automorphism of $K$ to get $y(1\theta) =  \theta \beta^3$ or $(1y)  \theta = \theta \beta^3$. So, if $y$ solves the $i=2$ case then $1y$ solves the $i=1$ case (and vice versa). And thanks for this answer! $\endgroup$ Commented Jun 11, 2021 at 12:29
According to SAGE, there are 6 integral points on the curve.
sage: EllipticCurve([0,0,1,0,1]).integral_points(both_signs=True)
[(1 : 1 : 1),(1 : 0 : 1),(1 : 2 : 1),(1 : 1 : 1),(11 : 37 : 1),(11 : 36 : 1)]

7$\begingroup$ The question is “What is the proof?” — so “Because the computer says so” seems a slightly unsatisfying answer, on its own. It would be greatly improved by some information about how SAGE computes this, since that’d provide at least a recipe for the proof. In 5 minutes of Googling I wasn’t easily able to work out what algorithm is used — the best I could find was the SAGE documentation and a couple of old MO answers: mathoverflow.net/a/46778/2273, mathoverflow.net/a/42044/2273 $\endgroup$ Commented Jun 10, 2021 at 15:13

2$\begingroup$ @PeterLeFanuLumsdaine: I agree. It is more than nothing though, and the algorithms of SAGE are pretty reliable. $\endgroup$ Commented Jun 10, 2021 at 15:50

$\begingroup$ Oh yes, I completely agree this answer is an excellent starting point! $\endgroup$ Commented Jun 10, 2021 at 15:54

2$\begingroup$ See also How to compute rational or integer points on elliptic curves. $\endgroup$ Commented Jun 10, 2021 at 16:05

$\begingroup$ The link to "SAGE documentation" in a comment above points to Elliptic curves over the rational numbers. Just posting this in case the URL shortener ends up breaking in the future. $\endgroup$ Commented Sep 5, 2022 at 11:44