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$.
1. We start by considering the polynomial \( f(x) = x^6 - x - 1 \). This polynomial is irreducible over \(\mathbb{Z}\) and even over \(\mathbb{F}_2\). Therefore, the quotient ring \(\mathbb{Z}[x]/(f(x))\) forms a field, specifically the finite field \(\mathbb{F}_{3^6}\) with 729 elements.

2. In \(\mathbb{F}_{3^6}\), every polynomial can be represented as an equivalence class of polynomials of degree less than 6. This is because any polynomial can be reduced modulo \(f(x)\), and since \(f(x)\) has degree 6, the remainder will have a degree less than 6.

3. The problem states that every polynomial is equivalent to exactly one of \(0, 1, x, x^2, \ldots, x^{727}\). This implies that the multiplicative group of the field \(\mathbb{F}_{3^6}^*\) is cyclic of order 728 (since \(\mathbb{F}_{3^6}\) has 729 elements, and the multiplicative group of a finite field of order \(q\) is cyclic of order \(q-1\)).

4. We need to find the largest integer \(n < 728\) for which there exists a polynomial \(p\) such that \(p^3 - p \equiv x^n \pmod{3}\).

5. Consider the equation \(p^3 - p = x^n\). In a finite field, the equation \(p^3 - p = 0\) has exactly 3 solutions (since it factors as \(p(p-1)(p+1) = 0\)). Therefore, \(p^3 - p\) can take on at most 3 distinct values in \(\mathbb{F}_{3^6}\).

6. Since \(\mathbb{F}_{3^6}^*\) is cyclic of order 728, let \(g\) be a generator of \(\mathbb{F}_{3^6}^*\). Then every nonzero element of \(\mathbb{F}_{3^6}\) can be written as \(g^k\) for some integer \(k\).

7. We need \(p^3 - p = g^n\). Since \(p^3 - p\) can take at most 3 distinct values, \(g^n\) must be one of these values. The largest \(n < 728\) for which this is possible is when \(g^n\) is the largest power of \(g\) that can be expressed as \(p^3 - p\).

8. The largest \(n\) for which \(g^n\) can be expressed as \(p^3 - p\) is \(n = 727\). This is because \(g^{727}\) is the largest power of \(g\) less than 728, and since \(g^{728} = 1\), \(g^{727}\) is the largest non-identity element in the cyclic group.

The final answer is \(\boxed{727}\).