Express each power of the root $\alpha$ of $\frac{\mathbb Z_2[x]}{\langle x^3+x^2+1\rangle}$ as linear combinations of $1, \alpha$ and $\alpha^2$

Question

There are $8$ elements in $\frac{\mathbb Z_2[x]}{\langle x^3+x^2+1\rangle} = GF(8)$

and this generates the set $\{0,1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1\}$

We're required to express $\alpha^1$ all the way up to $\alpha^7$ as linear combinations of $1, \alpha$ and $\alpha^2$

$\alpha^1 = \alpha$
$\alpha^2 = \alpha^2$
$\alpha^3 = \alpha^2 + 1$
$\alpha^4 = \alpha^2+\alpha+1$
$\alpha^5 = \alpha+1$
$\alpha^6 = \alpha^2+\alpha$
$\alpha^7 = 1$

I'm really not seeing where these combinations are coming from. Why is $\alpha^3 = \alpha^2+1$?

Answer 1

If $\alpha$ is a root of $x^3+x^2+1$, then $\alpha^3+\alpha^2+1=0$, so $\alpha^3=\alpha^2+1$ (since $1=-1$ over $\mathbb{Z}_2$).
From here: $$\begin{array}{l} \alpha^4=\alpha\alpha^3=\alpha(\alpha^2+1)=\alpha^3+\alpha=\alpha^2+\alpha+1\\ \alpha^5=\alpha\alpha^4=\alpha^3+\alpha^2+\alpha=\alpha^2+1+\alpha^2+\alpha=\alpha+1\\ \alpha^6=\alpha\alpha^5=\alpha^2+\alpha\\ \alpha^7=\alpha\alpha^6=\alpha^3+\alpha^2=\alpha^2+1+\alpha^2=1 \end{array}$$ (using $1+1=0$ over $\mathbb{Z}_2$)

Answer 2

Perhaps simplest: use the recursion $\rm\ \alpha^{n+3}\! = \alpha^{n+2} + \alpha^n\ $ arising from $\,\alpha^n\,$ times $\:\alpha^3 = \alpha^2 + 1$.

Alternatively, more generally, one easily calculates the effect of multiplying by $\rm\,\alpha\,$ as follows

$$\begin{eqnarray}\rm \alpha^n &=\,&\rm a\,\ +\,\ b\, \alpha\ +\, c\, \alpha^2\\ \rm \Rightarrow\ \ \alpha^{n+1} &=\,&\rm a\, \alpha + b\, \alpha^2 + c (\alpha^2\! +\! 1)\ \ \ by\ \ \ \alpha^3 = \alpha^2+1 \\ &=\,&\rm c + a\, \alpha + (b\!+\!c)\,\alpha^2 \end{eqnarray}$$

So $\rm\:(a,b,c)\to (c,a,b\!+\!c),\:$ i.e. rotate right $\rm\:(a,b,c)\to (c,a,b)\:$ then add the first into the last.

The same ideas generalize to arbitrary degree.