2008 iTest Problems/Problem 100

Let $\alpha$ be a root of $x^6-x-1$ , and call two polynomials $p$ and $q$ with integer coefficients $\textit{equivalent}$ if $p(\alpha)\equiv q(\alpha)\pmod3$ . It is known that every such polynomial is equivalent to exactly one of $0,1,x,x^2,\ldots,x^{727}$ . Find the largest integer $n<728$ for which there exists a polynomial $p$ such that $p^3-p-x^n$ is equivalent to $0$ .