Factorising a Congruence
Let
\[b\]
be a solution of the Polynomial congruence \[P(x) \equiv 0 \; (mod \; p)\]
where \[P(x)\]
is a polynomial of degree \[k \ge 1\]
. Then \[P(x) \equiv (x-b)P_1(x) \; (mod \; p)\]
where \[P_1(x)\]
is a polynomial of degree of \[k-1\]
.Proof
Suppose
\[P(x)=c_kx^k+c_{k-1}x^{k-1}+...+c_1x+c_0, \; c_k \neq 0 \; (mod \; p)\]
.\[P(b) \equiv 0 \; (mod \; p)\]
so we can write\[\begin{equation} \begin{aligned} P(x) & \equiv P(x)-P(b) \; (mod \; p) \\ & \equiv (c_kx^k+c_{k-1}x^{k-1}+...+c_1x+c_0)-(c_kb^k+c_{k-1}b^{k-1}+...+c_1b+c_0) \\ & \equiv c_k(x^k-b^k)+c_{k-1}(x^{k-1}-b^{k-1})+...+c_1(x-b) \\ & \equiv c_k(x-b)(X^{k-1}+x^{k-2}b+x^{k-3}b^2+...+xb^{k-2}+b^{k-1} \\ &+ c_{k-1}(x-b)(X^{k-2}+x^{k-3}b+x^{k-4}b^2+...+xb^{k-3}+b^{k-2}+...+c_1(x-b) \\ & \equiv (x-b)(c_k(X^{k-1}+x^{k-2}b+x^{k-3}b^2+...+xb^{k-2}+b^{k-1} \\ &+ c_{k-1}(X^{k-2}+x^{k-3}b+x^{k-4}b^2+...+xb^{k-3}+b^{k-2}+...+c_1) \\ & \equiv (x-b)P_1(x) \; (mod \; p)\end{aligned} \end{equation}\]
where
\[P_1(x)\]
is a polynomial of degree \[k-1\]
. 
