# Math Help - Proof using induction

1. ## Proof using induction

Prove that if $f(x) \equiv 0(mod p)$ has $j$ solutions $x \equiv a_{1}, x \equiv a_{2},...,
x \equiv a_{j} (mod p)$
, there is a polynomial $q(x)$ such that $f(x) \equiv (x - a_{1})
(x - a_{2}) ... (x - a_{j})q(x)(mod p)$
.

I feel that I need to somehow show that there is a polynomial $q_{1}(x)$ such that $f(x) \equiv (x-a_{1})q_{1}(x)(mod p)$and that $q_{1}(x) \equiv 0 (mod p)$has solutions $x=a_{2}, x=a_{3}, ..., x=a_{j} (mod p)$, but I don't know start from there and finish the proof using induction.

2. 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!