We proceed by induction on the degree of . If has degree 1, there is nothing to show because it is already in the form . So suppose it holds for all polynomials having degree . Let be of degree , and suppose is a solution. Then . So we have

where is of degree . Now use the fact that is prime to show that any other roots of must in fact be roots of , and apply the induction hypothesis to obtain the desired factorization for .

Hope that helps!