Proof using induction

We proceed by induction on the degree of $f$ . If $f$ has degree 1, there is nothing to show because it is already in the form $x-a$ . So suppose it holds for all polynomials having degree $\leq n-1$ . Let $f(x)=c_0+c_1x+...+c_nx^n$ be of degree $n$ , and suppose $x \equiv a \mod p$ is a solution. Then $0\equiv f(a) \equiv c_0+c_1a+...+c_na^n$ . So we have

$f(x)\equiv f(x)-f(a) \equiv c_1(x-a)+...+c_n(x^n-a^n)$

$\equiv (x-a)(c_1+c_2(x+a)+...+c_n(x^{n-1}+x^{n-2}a+...+xa^{n-2}+a^{n-1}))$

$\equiv (x-a)g(x)$

where $g(x)$ is of degree $\leq n-1$ . Now use the fact that $p$ is prime to show that any other roots of $f(x)$ must in fact be roots of $g(x)$ , and apply the induction hypothesis to obtain the desired factorization for $f(x)$ .

Hope that helps!