If $q(A) = 0$, then $q$ is divisible by the minimal polynomial of $A$ If $A$ is a linear transformation with minimal polynomial $p(x)$, and if $q(x)$ is a polynomial such that $q(A)=0$, then show that $q$ is divisible by $p$.
 A: Hint:
Use polynomial long division to write $q=ps+r$, where $r$ is a polynomial with degree less than the degree of $p$. Then use the fact that $q$ annihilates $A$. 
What can you conclude about $r$?
A: This is a basic property of minimal polynomials; it should be explained in any textbook right near the point minimal polynomials are introduced. Without knowing this property, it is not even clear why the minimal polynomial of $T$ is unique (hence well defined), namely why among the nonzero polynomials of minimal degree that annihilate $T$ there is exactly one monic polynomial (which then is by definition the minimal polynomial).
In any case the proof is the staple proof for statements of the type "for some property of polynomials$~P$, a nonzero polynomial of minimal degree with the property divides any polynomial with that property", with the property here being "$P[A]=0$". Of course this is not true for just any property, but it suffices that the property for two polynomials $S$ and $P\neq0$ implies the property for the remainder$~R$ of the division of $S$ by$~P$, namely such that $S=PQ+R$ for some polynomial $Q$ and $\deg R<\deg S$.
Here concretely is the proof for the property of annihilating $A$, i.e., $P[A]=0$.

Let $P$ be a nonzero polynomial of minimal degree such that annihilates $A$, and $S$ another polynomial that annihilates $A$. For the remainder $R$ of the division of $S$ by $P$ one has $R=S-PQ$ and therefore $R[A]=S[A]-P[A]\circ Q[A]=0-0\circ Q[A]=0$, that is $R$ annihilates $A$ too. Since $\deg R<\deg P$ by definition of remainder, and $\deg P$ is minimal among nonzero annihilating polynomials, one must have $R=0$, in other words $P$ divides$~S$.

Such$~P$ (being nonzero) has a unique scalar multiple that is monic, which is the minimal polynomial of $A$. By the property just established, it is the unique monic polynomial annihilating$~A$ of degree${}\leq\deg P$ (other monic polynomial multiples of $P$ have strictly higher degree), so it is independent of our choice of$~P$, and well defined (under the sole assumption that there are any nonzero annihilating polynomials at all, which is true for all linear operators$~A$ on a finite dimensional vector space.)

A completely similar proof is used to show that the least common multiple of two (or more) polynomials divides any of their common multiples, or that a nonzero polynomial combination $SA+TB$ of two given polynomials $A,B$ of minimal possible degree divides any polynomial combination of $A,B$ (the latter made monic gives $\gcd(A,B)$). Each time the fact that the property in question passes to the quotient of a polynomial division, is based on the fact that it passes to polynomial multiples and to differences of polynomials with the property; technically, the property defines an ideal of the polynomial ring $K[X]$, and the proof is that of the fact that $K[X]$ is a principal ideal domain (where $K$ is a field).
