Let $F=\mathbf Z_2$ and let $f(x)=x^3+x+1 \in F[x]$ and let a be a zero of $f(x)$ in some extension of $F$

Question

a) How many elements does $F(a)$ have?

b) Express $a^5, a^{-2}, a^{100}$ in the form $c_2a^2+c_1a+c_0$

I know that $F(a)$ has 8 elements since $f(x)$ has no zeros in $\mathbf{Z_2}$ and by a theorem that states : $$F(a)\cong F[x]/<p(x)>$$ for $p(x)$ irreducible over F, with a being a zero of p(x) on some extension E of F, there are two choices for each coefficient. Theorem then states that all elements of can be written in the form: $$c_{n-1}a^{n-1}+c_{n-2}a^{n-2}+...+c_1a+c_0,$$ where $c_0, c_1,..., c_{n-1} \in F$

I need to know how to do b). I have the answer for it and I don't understand how is it that $a^5=a^2+a+1$ for example. I need an explanation of how this is done.

Answer 1

Using the form $F[x]/(p)$, the element $a$ is represented by $x$. Therefore we have $$a^5 = x^5 = (x^2-1)p(x) -x^2 +x+1\equiv -x^2+x+1 = -a^2+a+1.$$ For $a^{-2}$, we are looking for a polynomial $q(x)\in F[x]$ such that $$x^2q(x)\equiv 1.$$ You can find out by trial and error (ask yourself: what is $x^2\cdot x^n$ for $n\le3$? And then find a good linear combination) that a solution is given by $x^2+x^3 = a^3+a^2$.

Answer 2

If $a$ is a zero of $x^3+x+1$, then $a^3=-a-1=a+1$, since we're working mod $2$.

Then, $a^4=a\cdot a^3=a(a+1)=a^2+a$.

Moreover, $a(a^2+1)=1$ and so $a^{-1}=a^2+1$ and $a^{-2}=(a^2+1)^2=a^4+1=a^2+a+1$.

Now, $a$ is a non-zero element in a field of $8$ elements. Hence, by Lagrange's theorem applied to the multiplicative group, we have $a^7=1$.

Therefore, $a^5=a^{-2}=a^2+a+1$ and $a^{100}=a^{100 \bmod 7}=a^2$.

You can avoid Lagrange's theorem by computing $a^5=a\cdot a^4=\cdots=a^2+a+1=a^{-2}$, which implies $a^7=1$.