Proof using induction

keityo · #1 $Old$ November 5th, 2009, 10:34 PM

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.

Bruno J. · #2 $Old$ November 5th, 2009, 10:46 PM

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!