If $x$ is a root of $x^2 + x + 1$ over $GF(4)$, then so is $x + 1$

Question

It's clear to me how $GF(4)$ can be gotten as the quotient ring of $GF(2)/X^2+X+1$. This leads to the four elements $0, 1, x, 1+x$. I'm struggling more as seen these ones as extending $GF(2)$ with the roots of the irreducible polynomial $x^2+x+1$ in $GF(2)$. Everywhere I've inspected better on existing answer here on that, I saw the claim:

if $x$ is a root, then $x+1$ is a root as well

It's not clear here what root means, here. I mean we can extend $GF(2)$ by one of the cube root of unity, so let's call it x. But then $x+1$ is NOT yet another root of $x^2+x+1$.

May you help better in understanding that, please?

Thanks in advance

Answer 1

You ask:

It's not clear here what root means, here

A number $a$ is a root of some polynomial $P$ if and only if $P(a) = 0$. Sometimes we say that $a$ is a “zero” of $P$, to emphasize this. The two terms mean the same thing.

Supposing that $a$ is a root of $x^2+x+1$, so that $a^2+a+1=0$, then $a+1$ is in fact the other root. Let's substitute $a+1$ for $x$ in $x^2+x+1$ and see what we get:

$$\begin{align} (a+1)^2 + (a+1) + 1 & = \\ (a^2 + 2a + 1) + (a + 1) + 1 & = \\ a^2 + 3a + 3 & = & \text{(because $GF(2)$)} \\ a^2 + a + 1 & = \\ 0 \end{align} $$

Another to see this is to explicitly multiply $(x-a)(x-(a+1))$ and see what you get. The $a$s all cancel out and leave you with $x^2+x+1$ as you ought.

Here's a third way to see this. Suppose $a$ is a cube root of unity. Straightforward calculations (which I leave to you) show that $a+1$ must also be a cube root of unity because $a+1 = a^2$.

---

(I wrote a blog article about extension fields of $GF(2)$ that examines these points in great detail; maybe it will help. Especially see the part that begins “we will [introduce] a new number, called $b$, which has the property that $b^2 + b + 1 = 0$. What are the consequences of this?”)

Answer 2

Some of the confusion here may stem from $x$ serving double-duty as both an element of $GF(2)[x]$ and as a root of the particular polynomial $f(x) := x^2 + x + 1$.

Being a little more precise, let $\alpha$ denote the image of $x$ under the quotient map (ring homomorphism) $$\pi : GF(2)[x] \to GF(4) := GF(2)[x] / \langle f(x) \rangle .$$ In this notation, that the elements of our field are $0, 1, \alpha, \alpha + 1$.

By construction $f(\alpha) = f(\pi(x)) = \pi(f(x)) = 0$, so $\alpha$ is a root of $f$, where we here regard $f$ as a polynomial in $GF(4)[x]$. Now, we check whether $\alpha + 1$ is a root of $f$:

\begin{align} f(\alpha + 1) &= (\alpha + 1)^2 + (\alpha + 1) + 1 \\ &= (\alpha^2 + 1) + (\alpha + 1) + 1 \\ &= \alpha^2 + \alpha + 1 \\ &= f(\alpha) \\ &= 0 . \end{align}

The second and third equalities use the fact that $GF(4)$ has characteristic $2$.