<s>[INST] Find all pairs of prime numbers $p$ and $q$ such that $\,p^2-p-1=q^3.$ 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.
 [/INST] 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.
</s>