<s>[INST] Division in finite fields Let's take $GF(2^3)$ as and the irreducible polynomial $p(x) = x^3+x+1$ as an example. This is the multiplication table of the finite field
I can easily do some multiplication such as $$(x^2+x)\cdot(x+1) = x^3 + x^2 + x +1 = x+1+x^2+x+2 = x^2$$
I am wondering how to divide some random fields such as $x^2 / (x+1)$. The result is $x^2+x$ (compare above). But how do I actually calculate this. Polynomial long division does not help be:



*

*Why don't I get $x+1$ as result? 

*How can I calculate $x / (x^2+x+1)$? The result should be $x+1$

 [/INST] Since any element of this field can be written as $ax^2+bx+c$ we write:
$\frac{x}{x^2+x+1}=ax^2+bx+c$
$x=(ax^2+bx+c)*(x^2+x+1)$
$x=ax^4+(a+b)x^3+(a+b+c)x^2+(b+c)x+c$
Use the fact that $x^3=x+1$ to further simplify.
$x=a(x^2+x)+(a+b)(x+1)+(a+b+c)x^2+(b+c)x+c$
$x=(b+c)x^2+(c)x+(a+b+c)$
Now solve for $a$, $b$, and $c$ by comparing each power of $x$.
$b+c=0$
$c=1$
$a+b+c=0$
Thus, $a=0$, $b=1$, and $c=1$.
So $\frac{x}{x^2+x+1}=x+1$
</s>