Cayley-Hamilton...
Solution 1:
Let $\lambda$ be any eigenvalue of a minimal counterexample $A$ and choose a basis so $$A=\begin{pmatrix}\lambda&*\\0&B\end{pmatrix}.$$
Let $m(x)$ and $n(x)$ be the minimal polynomials of $A$ and $B$, respectively. Let $q(x)$ be the characteristic polynomial of $B$, where we can suppose that $n(x)|q(x)$.
Then $$(A-\lambda)n(A)=\begin{pmatrix}0&*\\0&*\end{pmatrix}\begin{pmatrix}n(\lambda)&*\\0&0\end{pmatrix}=0$$ and therefore $m(x)|n(x)(x-\lambda)|q(x)(x-\lambda)=p(x)$.