State and prove the Cayley-Hamilton Theorem.

Let $A$ be an $n \times n$ complex matrix. Using division of polynomials, show that if $p(x)$ is a polynomial then there is another polynomial $r(x)$ of degree at most $(n-1)$ such that $p(\lambda)=r(\lambda)$ for each eigenvalue $\lambda$ of $A$ and such that $p(A)=r(A)$.

Hence compute the $(1,1)$ entry of the matrix $A^{1000}$ when

$$A=\left[\begin{array}{ccc} 2 & -1 & 0 \\ 1 & -1 & 1 \\ -1 & -1 & 1 \end{array}\right]$$