Exercise 2.7.4 (Successive factorizations)

Proof. of lemma. Since $x-a$ is monic, there exists polynomials $q,r$ in $\mathbb{Z}[x]$ such that

Since $\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(r)<1$, $r$ is a constant integer $k\in \mathbb{Z}$ (the case $k=0$ corresponds to $\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(r)=-\infty$).

Then $f(x)=(x-a)q(x)+k$, thus $f(a)=k\equiv 0(\mathit{mod}p)$, therefore $f(x)\equiv (x-a)q(x)(\mathit{mod}p)$. The lemma is proved. □

Proof. Suppose now that $f(x)\equiv 0(\mathit{mod}p)$ has $j$ solutions $a_1,\dots ,a_j$, where $a_i\not\equiv a_j(\mathit{mod}p)$ if $i\ne j$.

We prove by induction for $k\in [[1,j]]$ the property

• If $k=1$, then the lemma shows that $f(x)\equiv (x-a_1)q(x)(\mathit{mod}p)$, for some polynomial $q(x)$. This proves $𝒫(1)$.

• Suppose that $𝒫(k)$ is true for some $k$, $1\le k<j$.

  Then $f(x)\equiv (x-a_1)\cdots (x-a_k)q_k(x)$ for some polynomial $q_k(x)\in \mathbb{Z}[x]$. Since $f(a_{k+1})\equiv 0(\mathit{mod}p)$,

  $$(a_{k+1}-a_1)\cdots (a_{k+1}-a_k)q_k(a_{k+1})\equiv 0(\mathit{mod}p).$$

  By hypothesis, $p\nmid a_{k+1}-a_1,\dots ,p\nmid a_{k+1}-a_k$, therefore $q_k(a_{k+1})\equiv 0(\mathit{mod}p)$. If we apply the lemma to $q_k$, we obtain that

  $$q_k(x)\equiv (x-a_{k+1})q_{k+1}(x),$$

  for some polynomial $q_{k+1}(x)\in \mathbb{Z}[x]$.

  So $f(x)\equiv (x-a_1)\cdots (x-a_k)(x-a_{k+1})q_{k+1}(x)$. This proves $𝒫(k+1)$.

• The induction is done. We conclude that $𝒫(k)$ is true for every $k\in [[1,j]]$. In particular, $𝒫(j)$ is true, so there exists some polynomial $q(x)=q_j(x)\in \mathbb{Z}[x]$ such that

  $$f(x)\equiv (x-a_1)(x-a_2)\cdots (x-a_j)q(x)(\mathit{mod}p).$$