<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] Since we want $$p^2-(2+3k+k^3)p+(3k^2+3k+1)=0$$ to have integer solutions its Discriminant has to be a perfect square
i.e. $k^2(k^4+6k^2+4k-3)$ has to be a perfect square thus
$k^4+6k^2+4k-3$ has to be a perfect square
But $(k^2+3)^2 \le k^4+6k^2+4k-3<(k^2+4)^2$ thus we have
$4k-3=9 \Rightarrow k=3$
</s>