Exercise 11.2.16

Proof.

$\text{∙}$

Suppose that $f$ is irreducible over ${𝔽}_2$. Then $F={𝔽}_2[x]∕⟨f⟩$ is a field with $2^r$ elements, so $F\simeq {𝔽}_{2^r}$. Then $\alpha =x+⟨f⟩\in F$ is a root of $f$ in $F$, and $F\simeq {𝔽}_{2^r}$, therefore ${\alpha }^{2^r}=\alpha$, so $\alpha$ is a root of $x^{2^r}-x$. Since $f$ is the minimal polynomial of $\alpha$ over ${𝔽}_2$, $f\mid x^{2^r}-x$.

$\text{∙}$

Conversely, suppose that $f\mid x^{2^r}-x$.

Since $x^{2^r}-x$ is a separable polynomial over ${𝔽}_2$, $f$ is also separable. Thus

$$f=f_1{f}_2\cdots f_k,$$

where $f_1,\dots ,f_k$ are monic irreducible polynomials such that $\gcd <!--\; FUNCTION\; APPLICATION\; -->(f_i,f_j)=1$ if $i\ne j$. We want to prove that $k=1$. By Exercise 10 (Chinese Remainder Theorem),

$${𝔽}_2[x]∕⟨f⟩\simeq {𝔽}_2[x]∕⟨f_1⟩\times \cdots {𝔽}_2[x]∕⟨f_k⟩.$$

Since $R_i={𝔽}_2[x]∕⟨f_i⟩$ is a field with $2^{d_i}$ elements ( $1\le i\le k$), where $d_i=\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(f_i)$, then $R_i\simeq {𝔽}_{2^{d_i}}$, and $d_1+\cdots +d_k=\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(f_1)+\cdots +\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(f_k)=\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(f)=r$. Thus

$${𝔽}_2[x]∕⟨f⟩\simeq {𝔽}_{2^{d_1}}\times \cdots \times {𝔽}_{2^{d_k}},d_1+\cdots +d_k=r.$$

Let $g_i$ a generator of ${({𝔽}_{2^{d_i}})}^{\text{∗}}$ for $i=1,\dots ,k$. Then $g_i^{2^{d_i}-1}=1$.

Write $\psi :{𝔽}_2[x]∕⟨f⟩\to {𝔽}_{2^{d_1}}\times \cdots \times {𝔽}_{2^{d_k}}$ the previously constructed ring isomorphism. There exists a coset $\beta \in {𝔽}_2[x]∕⟨f⟩$ such that $\psi (\beta )=(g_1,\dots ,g_k)$.

Let $\alpha =x+⟨f⟩$ be the coset of $x$. Then $f(\alpha )=0$, and since $f\mid x^{2^r}-x$, ${\alpha }^{2^r}=\alpha$.

Moreover, $\beta =h(\alpha )$, where $h\in {𝔽}_2[x],\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(h)<r$. Since the characteristic is 2,

$${\beta }^{2^r}=h{(\alpha )}^{2^r}=h({\alpha }^{2^r})=h(\alpha )=\beta .$$

By the isomorphism $\psi$, $\psi {(\beta )}^{2^r}=\psi (\beta )$, thus ${(g_1,\dots ,g_k)}^{2^r}=(g_1,\dots ,g_k)$, so $g_1^{2^r}=g_1,\dots ,g_k^{2^r}=g_k$, with $g_i\ne 0$ in the field $R_i$, so

$$g_1^{2^r-1}=1,\dots ,g_k^{2^r-1}=1.$$

Since the order of $g_i$ is $2^{d_i}-1$,

$$2^{d_1}-1\mid 2^r-1,\dots ,2^{d_k}-1\mid 2^r-1.$$

Recall that $2^n-1\mid 2^m-1$ implies $n\mid m$. Indeed, write $m=\mathit{nq}+s,0\le s<n$. Then $2^m\equiv 1(\mathit{mod}{2}^n-1)$ (and $2^n\equiv 1(\mathit{mod}{2}^n-1)$), so $1\equiv 2^m={(2^n)}^q{2}^s\equiv 2^s(\mathit{mod}{2}^n-1)$, thus $2^n-1\mid 2^s-1,0\le s<n$, therefore $s=0$, so $n\mid m$.

Consequently,

$$d_1\mid r,\dots ,d_k\mid r.$$

But $r$ is prime! So $d_i=1$ or $d_i=r$ for all $i=1,\dots ,k$.

Since $d_1+\cdots +d_k=r$ with $d_i>0$, if there is an index $i$ such that $d_i=r$, then $k=1$. In this case $f=f_1$ is irreducible.

It remains the case where $d_i=1$ for all $i=1,\dots ,k$. Then $f_i=x-a_i,a_i\in {𝔽}_2$, so

$$f=(x-a_1)\cdots (x-a_k),a_i\in {𝔽}_2$$

splits completely over ${𝔽}_2$. But this is impossible, since $f=x^r+x^s+1$ has no root in ${𝔽}_2$. Therefore $f$ is irreducible over ${𝔽}_2$.