Find values of $p$ such that $p^2-p+1$ is cubic? Find all prime numbers such that $p^2-p+1$ is a cubic number. I've tried substituting values of $x$ for $p^2-p+1 = x^3$. 
This gave me a few values, which were small. As values of $x$ ranged higher and higher, it was tedious to find values of $p$ that satisfied this condition. To my imminent horror, I realized that most of these values of $p$ where in fact NOT prime numbers. 
Can someone guide me through the solution, as I prefer to use a slick solution, rather than using brute force? After the solution, can someone point me towards resources for solving problems like this?
 A: How about finding all integers $y$ with $x^3=y^2-y+1$
instead? Then $x^3=(y+\omega)(y+\overline\omega)$
where $\omega=\frac12(-1+i\sqrt 3)$ is a cube root of unity.
we have two factorisations in the ring $R=\Bbb Z[\omega]$.
This ring is a unique factorisation domain, but has six units $\pm\omega^j$.
The elements $y+\omega$ and $y+\overline\omega$ have greatest
common divisor $1$ or $i\sqrt3=\omega-\omega^2$. In the former case, $y+\omega$
is a unit times a cube, and we can reduce to $y+\omega=(a+b\omega)^3$,
$y+\omega=\omega(a+b\omega)^3$ or $y+\omega=\omega^2(a+b\omega)^3$.
In the latter case, $y+\omega$ is $i\sqrt3$ times a unit
times a cube, and then $y+\omega=\omega^j(\omega-\omega^2)(a+b\omega)^3$.
This reduces to six cases. I'll just look at one: $y+\omega=(a+b\omega)^3$.
This can be written as
$$\frac{2y-1+i\sqrt3}{2}=\left(\frac{c+d\sqrt{-3}}2\right)^3.$$
Therefore $4(2y-1)=c^3-9cd^2$ and $4=3c^2d-3d^3$. That's easy
enough. No solutions.
Five more cases to go!
A: This is a comment rather than an answer: the equation $y^2-y=x^3-1$ can be seen as a Weierstrass form of an elliptic curve over $\Bbb{Q}$ and there is a systematic way to compute the integral points on these elliptic curves, see Silverman's book on elliptic curves perhaps. You can also use some math softwares to help you do these tedious stuffs, for example MathSage told me that the only solution to your question is $(x,y)=(7,19)$. If you don't care about the proof, this is a fairly good choice.
A: Here is a solution using simpler tools.
Our starting point is
$$p^2 - p + 1 = x^3$$
with $p$ prime, and $x$ is an integer.
As the smallest prime is 2, note that 
$$x^3 = p^2 - p + 1 \ge 2^2 - 2 + 1 = 3 \quad \rightarrow \quad x \ge 3^{1/3} > 1$$
$$p^2 > p^2 - p + 1 = x^3 \quad \rightarrow \quad p > x^{3/2} > x $$
Since $p$ being prime is important, this hints we should try to rearrange the equation to factor as much as possible.
$$
\begin{eqnarray}
p^2 - p + 1 &=& x^3 \\
p^2 - p &=& x^3 - 1 \\
p(p-1) &=& (x-1)(x^2+x+1)
\end{eqnarray}
$$
Because $p$ is prime and divides the left hand side, it must divide the right hand side as well. Since $p>x$, this means $p$ cannot divide $(x-1)$ and therefore $(x^2+x+1)$ must be a multiple of $p$. Let's call this multiple $m$. 
So we now have two equations
$$
\begin{eqnarray}
mp &=& (x^2+x+1) \\
(p-1) &=& m(x-1)
\end{eqnarray}
$$
Because $p>x$ the second equation makes it clear that $m>1$, and since it is an integer $m \ge 2$. Note also that $(x^2 + x +1)$ cannot be even, thus raising the limit further: $m \ge 3$.
Eliminating $p$ to get a quadratic on $x$
$$
\begin{eqnarray}
p &=& mx - m + 1 \\
m(mx - m + 1) &=& (x^2+x+1) \\
0 &=& x^2 + (1-m^2)x + (m^2-m+1)
\end{eqnarray}
$$
For the quadratic equation to have an integer solution, the discriminant must be a square value
$$
\begin{eqnarray}
(1-m^2)^2 - 4(m^2-m+1) &=& (1 - 2m^2 + m^4) - 4(m^2-m+1) \\
                       &=& m^4 - 6m^2 +4m-3
\end{eqnarray}
$$
Requiring this to be a square integer is quite restrictive, which is easier to see if we denote the square as $(m^2 - k)^2 = m^4 -2km^2 + k^2$. Using this along with the fact that $m \ge 3$ (thus $m^2 \ge 3m$), we can see
$$ m^4 - 6m^2 +4m-3 < m^4 - 4m^2 - 3 < (m^2 - 2)^2 $$
and
$$ m^4 - 6m^2 +4m-3 \ge m^4 - 6m^2 -3m + 18 > m^4 -8m^2 + 18 > (m^2 - 4)^2 $$ 
therefore
$$m^4 - 6m^2 +4m-3 = (m^2 - 3)^2 = m^4 - 6m^2 + 9$$
$$4m = 12 \quad \rightarrow \quad m=3$$
Now putting this back in our quadratic equation for $x$
$$ 0 = x^2 + (1-m^2)x + (m^2-m+1) = x^2 - 8x + 7 = (x-1)(x-7) $$
As $x>1$, this means the only solution is
$$x=7 \quad \rightarrow \quad p=m(x-1)+1=19. $$
