Exercise 4.2.6

Proof. If $f$ is reducible, of degree $n$, $f=\mathit{gh},g,h\in F[x]$, where $1\le \mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(g)\le \mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(h)\le n-1$.

As $\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(g)+\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(h)=n$, $2\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(g)\le n,\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(g)\le n∕2$. If we multiply $g,h$ by appropriate constants, we can suppose that $g$ is monic.

So $f$ is reducible iff there exists a monic factor of $f$ of degree $d$, $d,1\le d\le n∕2$.

As $F$ is finite, with cardinality $q$, we can list all monic polynomials of degree $k$, of the form $p=x^k+a_{k-1}{x}^{k-1}+\cdots +a_0$, by listing all $q^k$ $k$-plets $(a_0,\cdots ,a_{k-1})$, and test the divisibility of $f$ by each such polynomial, for every value of $k,1\le k\le n∕2$.

If $f$ is irreducible, the number of polynomial division to prove the irreducibility is so

□