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$ 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$?
 A: 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$)
A: 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.
