Find an irreducible polynomial of degree $21$ in $\mathbb{F}_2[x]$

Question

Note: this is from a paper on Galois Theory, so I believe the technique will come from Galois... Possibly.

I am going to reduce it to the monic case: $x^{21}+a_{20}x^{20}+... a_0$ where all $a_i$ belong to $\{0,1\}$ . I was thinking of trying to generate a polynomial that would satisfy Eisenstein's criterion but it cannot have any prime coefficients.

The easiest starting points are $x^{21}+x$, $x^{21}+x+1$, $x^{21}+x^2$ ...etc

I do not know how to check that these are irreducible without Eisenstein's criterion.. Is it true that since the highest power is odd, if it were irreducible, then it would have a linear factor. So can we just plug in values of $0$ and $1$ until we find a polynomial that gives us a non -zero answer?

So for example, can we say that $f(x)=x^{21}+x+1$ is irreducible, since $f(0)=f(1)=1 \neq 0$?

Is it possible to use Galois Theory to answer these questions?

Answer 1

The following trick springs to mind.

We know that the minimal polynomials of seventh roots of unity are the cubic irreducibles $$ p_1(x)=x^3+x+1\qquad\text{and}\qquad p_2(x)=x^3+x^2+1. $$

Now, because $2$ is of order $21$ modulo $49$ (leaving it to you to check that), we can deduce (Galois theory is all we need here) that:

• The 49th roots of unity generate the field $\Bbb{F}_{2^{21}}$.
• Hence their minimal polynomials are irreducible of degree $21$.
• Hence their minimal polynomials are (drums, please) $$ p_1(x^7)=x^{21}+x^7+1\qquad\text{and}\qquad p_2(x^7)=x^{21}+x^{14}+1. $$

Answer 2

About your very last question (with fields extensions theory, in fact):

we know $\;\Bbb F_{2^{21}}\cong\Bbb F_2[x]/{p(x)}\;$ , with $\;p(x)\in\Bbb F_2[x]\;$ irreducible. But we also know that $\;\Bbb F_{2^{21}}\;$ is the

splitting field over its prime field of $\;x^{2^{21}}-x\in\Bbb F_2[x]\;$ , so it must be that $\;p(x)\;$ is among the

divisors of this last polynomial.

Anyway, it doesn't look like an enjoyable task.

Answer 3

Using the Berlekamp algorithm it follows that $$ x^{21}+x+1=(x^{14} + x^{12} + x^7 + x^6 + x^4 + x^3 + 1)(x^7 + x^5 + x^3 + x + 1) $$ over $\mathbb{F}_2$, hence it is reducible. However, $$ g(x)=x^{21}+x^2+1 $$ is irreducible over $\mathbb{F}_2$.

Answer 4

We may take two irreducible polynomials over $\mathbb{F}_2$: $$ p_\alpha(x)=x^3+x+1,\qquad p_\beta(x)=x^7+x+1 $$ and by assuming that $\alpha$ is a root of $p_\alpha$, $\beta$ is a root of $p_\beta$, just compute the minimal polynomial, over $\mathbb{F}_2$, of $\alpha+\beta$. Since $[\mathbb{F}_2(\alpha):\mathbb{F}_2]=3,\, [\mathbb{F}_2(\beta):\mathbb{F}_2]=7$ and $\gcd(3,7)=1$, $[\mathbb{F}_2(\alpha+\beta):\mathbb{F}_2]=21$ as wanted.

We just have to represent $(\alpha+\beta)^k$, for $k\in\{0,1,2,\ldots,20,21\}$, as a linear combination of $\alpha^i \beta^j$, with $i\in\{0,1,2\}$ and $j\in\{0,1,\ldots,6\}$, then perform Gaussian elimination.