Factorisation of Polynomials Modulo p
Let
\[p\]
be prime and let \[b_1, \; b_2,...,b_r\]
be incongruent solutions of \[P(x) \equiv 0 \; (mod \; p)\]
where \[P(x)\]
is a polynomial of degree \[k\]
. Then \[P(x) \equiv (x-b_1)(x-b_2)...(x-b_r)P_r(x) \; (mod \; p)\]
where \[P_r(x)\]
is a polynomial of degree \[k-r\]
.Proof
Lagrange's Theorem tells us that
\[P(x) \equiv (x-b_1)P_1(x) \; (mod \; p)\]
where \[P_1(x)\]
is a polynomial of degree \[k-1\]
.\[P(b_2) \equiv 0 \; (mod \; p) \rightarrow (b_2-b_1)P_1(b_2) \equiv 0 \; (mod p)\]
\[p\]
does not divide \[b_2-b_1\]
since \[b_1, \; b_2\]
are incongruent modulo \[p\]
, hence \[P_1(b_2) \equiv 0 \; (mod \; p)\]
by Euclid's Lemma. We can use the Factorising Theorem for polynomials to obtain \[P_1(x) \equiv (x-b_2) P_2(x) \; (mod \; p) \equiv (x-b_1)(x-b_2)P_2(x) \; (mod \; p)\]
where \[P_2(x)\]
is a polynomial of degree \[k-2\]
.The result is reached when all
\[r\]
solutions have been processed in this way. 
