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$


If we have a field $K = F[X]/p(X)$, then we can compute the inverse of $\overline{q(X)}$ in $K$ as follows.
Since $p$ is irreducible, either $q$ is zero in $K$ or $(p,q)=1$. By the Euclidean algorithm, we can find $a,b$ such that $a(X)p(X) + b(X)q(X) = 1$.  Then $\overline{b(X)} \cdot \overline{q(X)} = \overline{1}$, so $\overline{b(X)}$ is the inverse of $\overline{q(X)}$.
In your example, the Euclidean algorithm gives us $(x+1)(x^3 + x + 1) + (x^2)(x^2 + x+1) = 1$ (modulo 2), so $(x^2+x+1)^{-1} = x^2$ and $\frac{x}{x^2+x+1} = x(x^2) = x^3 = x+1$.
