List the elements of the field $K = \mathbb{Z}_2[x]/f(x)$ where $f(x)=x^5+x^4+1$ and is irreducible

Question

Since $\dim_{\mathbb{Z}_2} K = \deg f(x)=5$, $K$ has $2^5=32$ elements. So constructing the field $K$, I get:

\begin{array}{|c|c|c|} \hline \text{polynomial} & \text{power of $x$} & \text{logarithm} \\\hline 0 & 0 & -\infty \\\hline 1 & 1 & 0 \\\hline x & x & 1 \\\hline x^2 & x^2 & 2 \\\hline x^3 & x^3 & 3 \\\hline x^4 & x^4 & 4 \\\hline x^4+1 & x^5 & 5 \\\hline x^4+x+1 & x^6 & 6 \\\hline x^4+x^2+x+1 & x^7 & 7 \\\hline x^4+x^3+x^2+x+1 & x^8 & 8 \\\hline x^3+x^2+x+1 & x^9 & 9 \\\hline x^4+x^3+x^2+x & x^{10} & 10 \\\hline x^3+x^2+1 & x^{11} & 11 \\\hline x^4+x^3+x & x^{12} & 12 \\\hline x^2+1 & x^{13} & 13 \\\hline x^3+x & x^{14} & 14 \\\hline x^4+x^2 & x^{15} & 15 \\\hline x^4+x^3+1 & x^{16} & 16 \\\hline x+1 & x^{17} & 17 \\\hline x^2+x & x^{18} & 18 \\\hline x^3+x^2 & x^{19} & 19 \\\hline x^4+x^3 & x^{20} & 20 \\\hline \end{array}

Have I constructed the field correctly? I'm sure the claim that $K$ has $32$ elements is true, yet when I actually construct the field, I only get $22$ elements as $x^{21} = x^0 = 1$.

Answer 1

The reason you have a problem is that $x^5+x^4+1$ is not irreducible in $\mathbb{Z}_2[x]$.

Thus, if $R=\mathbb{Z}_2[x]/(x^5+x^4+1)$, then $R^\times$ is not (as you would have expected if the polynomial were irreducible) a cyclic group of order $31$, so the fact that $x^{21}\equiv 1\bmod (x^5+x^4+1)$ is not surprising at all.

In fact, $x^5+x^4+1=(x^2+x+1)(x^3+x+1)$ in $\mathbb{Z}_2[x]$, so that $$\mathbb{Z}_2[x]/(x^5+x^4+1)\;\cong\;\mathbb{Z}_2[x]/(x^2+x+1)\oplus \mathbb{Z}_2[x]/(x^3+x+1)\;\cong\;\mathbb{F}_4\oplus\mathbb{F}_8$$ so that for unit groups, $$\mathbb{Z}_2[x]/(x^5+x^4+1)^\times\;\cong\;\mathbb{F}_4^\times\oplus\mathbb{F}_8^\times\;\cong\;\mathbb{Z}/3\mathbb{Z}\oplus\mathbb{Z}/7\mathbb{Z}\;\cong\;\mathbb{Z}/21\mathbb{Z}$$ Again, the ring $R=\mathbb{Z}_2[x]/(x^5+x^4+1)$, although having $32$ elements, is not a field, and therefore the unit group $R^\times$ is smaller than $R\setminus\{0\}$.

Even though you (completely coincidentally) chose a polynomial $x^5+x^4+1$ such that $x\in R^\times$, and such that $R^\times$ was cyclic, and such that $x$ was in fact a generator for $R^\times$, it could not help the fact that since $R^\times$ has $21$ elements and $R\setminus\{0\}$ has $31$ elements, you cannot get all the elements of $R\setminus\{0\}$ by successive powers of $x$.

---

Now, as to how to list elements.

In general, if $f\in \mathbb{Z}_p[x]$ is any polynomial of degree $n$, whether it is irreducible or not, then the $p^n$ elements of $\mathbb{Z}_p[x]/(f)$ are easily produced as the cosets $$a_0+a_1x+\cdots+a_{n-1}x^{n-1}+(f),\qquad a_0,a_1,\ldots,a_{n-1}\in\mathbb{Z}_p$$ Of course, $f$ is irreducible $\iff$ $\mathbb{Z}_p[x]/(f)$ is a field, but the elements of $\mathbb{Z}_p[x]/(f)$ are always simple to write down. It's the choice of $f$ that determines the additive and multiplicative structure.

Answer 2

One problem is, that you need to list all polynomials $f(x)\in \mathbb{F}_2[x]$ of degree $n\le 4$. This gives $2^{4+1}=32$ polynomials. For degree $5$, and hence higher degree, you can "reduce" the degree of the polynomial by the rule $x^5:=-x^4-1=x^4+1$. For example, the polynomial $x^3+1$ is missing in your list.

Edit: And yes, $x^5+x^4+1=(x^2+x+1)(x^3+x+1)$ here is not irreducible !

Answer 3

Elaborating more on the answer of Burde and generalizing:

Let $F$ be any finite field with $q$ elements, and $f(x)$ an irreducible polynomial from $F[X]$, say of degree $m$. Then the quotient ring by the principal ideal generated by $f(x)$ is in fact a field, has $q^m$ elements and the elements of this field is the set of all polynomials of degree${}<m$ with coefficients in $F$ (rather the cosets represented by them).

They are $q^m$ in number: this follows from the fact that two polynomials of degree less than $m$have their difference also a polynomial of degree less than $m$ and hence cannot be a multipleof a polynomial of degree $m$.

They are all the elements of the field because: the coset represented by a general polynomial $g(x)$ of degree$ \geq m$ is the same as the coset of $r(x)$ where $r(x)$ is obtained by Euclidean division with remainder: $g(x) = h(x) f(x) + r(x)$. (That is try to divide $g(x)$ by $f(x)$, getting quotient $h(x)$ and a remainder polynomial of degree less than the degree of $f(x)$.