I'm preparing a mathematical olympiad and our group is stuck in this problem. Here is all we've done:
First, let's rewrite the equation
$$p^2-p-1=q^3\Rightarrow p(p-1)=(q+1)(q^2-q+1)$$
It's obvious that $q$ must be less than $p$. Then, $p|(q^2-q+1)$ and then equation is of the form
$$p-1=k(q+1)$$
For some integer $k$. Putting that onto the first equation
$$\left(\frac{p-1}{k}-1\right)^3=q^3=p^2-p-1$$
Which is the same as
$$p^2-(2+3k+k^3)p+(3k^2+3k+1)=0$$
Since $p$ is prime $p|3k^2+3k+1$, a possible solution is $p=3k^2+3k+1$. Substituting
\begin{align*}
(3k^2+3k+1)^2-(2+3k+k^3)(3k^2+3k+1)+3k^2+3k+1=-k^2(k-3)(3k^2+3k+1)=0
\end{align*}
$k$ cannot be 0, so it's unique possible integer value is $3$ and $p=37$. Solving, $q=11$ which is a valid solution but we don't know if there are more or how to prove there aren't more, please help us continue.
Best Answer
You already have $$q^2-q+1=pk\quad\text{and}\quad p-1=k(q+1)$$ where $k$ is a positive integer.
Eliminating $p$ gives $$q^2-q+1=(kq+k+1)k,$$ i.e. $$q^2+(-1-k^2)q-k^2-k+1=0$$ to have $$q=\frac{k^2+1+\sqrt{k^4+6k^2+4k-3}}{2}$$
Note here that we get, for $k\gt 3$, $$k^2+3\lt \sqrt{k^4+6k^2+4k-3}\lt k^2+4$$ from which we have to have $k=1,2,3$.
For $k=1$, $\sqrt{k^4+6k^2+4k-3}=\sqrt 8\not\in\mathbb Z$
For $k=2$, $\sqrt{k^4+6k^2+4k-3}=\sqrt{45}\not\in\mathbb Z$
For $k=3$, $q=11,p=37$.
Hence, $\color{red}{(p,q)=(37,11)}$ is the only solution.