Proof using induction

• Nov 5th 2009, 08:34 PM
keityo
Proof using induction
Prove that if $\displaystyle f(x) \equiv 0(mod p)$ has $\displaystyle j$ solutions $\displaystyle x \equiv a_{1}, x \equiv a_{2},..., x \equiv a_{j} (mod p)$, there is a polynomial $\displaystyle q(x)$ such that $\displaystyle 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 $\displaystyle q_{1}(x)$ such that $\displaystyle f(x) \equiv (x-a_{1})q_{1}(x)(mod p)$and that $\displaystyle q_{1}(x) \equiv 0 (mod p)$has solutions $\displaystyle 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.
• Nov 5th 2009, 08:46 PM
Bruno J.
We proceed by induction on the degree of $\displaystyle f$. If $\displaystyle f$ has degree 1, there is nothing to show because it is already in the form $\displaystyle x-a$. So suppose it holds for all polynomials having degree $\displaystyle \leq n-1$. Let $\displaystyle f(x)=c_0+c_1x+...+c_nx^n$ be of degree $\displaystyle n$, and suppose $\displaystyle x \equiv a \mod p$ is a solution. Then $\displaystyle 0\equiv f(a) \equiv c_0+c_1a+...+c_na^n$. So we have

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

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

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

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

Hope that helps!