GCDs for the polynomial ring over a Galois field. You can find many examples of computing the inverse of an element inside a Galois field. (For example here)
What happens if we look at the polynomial ring over a Galois field and would like to compute gcd of two elements? Since this is a euclidean domain the GCD should be well-defined.
Let's say we have $\mathbb{F}_8$ as the Galois field. Since $\mathbb{F}_8$ is isomorphic to $\mathbb{F}_2[X]/(X^3+X+1)$, I can think about the elements of $\mathbb{F}_8$ as the polynomials $aX^2+bX+c$ with $a,b,c \in \mathbb{F}_2$.
Now we look at the polynomial ring $\mathbb{F}_8[Y] \cong \mathbb{F}_2[X]/(X^3+X+1) [Y] \cong \mathbb{F}_2[X,Y]/(X^3+X+1)$. (Are these congruences correct?)
So elements of $\mathbb{F}_8[Y]$ are for example $Y^3+X+1$, or just $Y^2$ or $Y+X^2$. Does anybody knows a way (or references) to calculate the gcd of some of this elements?
Calculating $\gcd(Y^3+X+1, Y^2)$ I only came this far:
$$ Y^3 + X + 1 = Y \cdot Y^2 + X +1$$
$$Y^2 = ?_a \cdot (X+1) + ?_b$$
If I should guess I would say that $2 \geq \deg_y(?_a) > \deg_y(?_b)$ has to be fulfilled, but I think this is impossible.
Any help or any ideas are appreciated! Thanks!

You ned rules for simplifying expressions in $\mathbf F_8$. With your setting, if you denote $\omega$ the congruence class of $X$ in $\mathbf F_2[X]/(X^3+X+1)$, you know that
$$\omega^3=\omega+1\qquad\text{(we're in characteristic }2),$$
so the last division is written as 
$$Y^2=(\omega+1)^{-1}Y^\cdot (\omega+1)+0.$$
Now, $\;\omega^3+\omega=1=\omega(\omega^2+1)=\omega(\omega+1)^2$, so $\;(\omega+1)^{-1}=\omega(\omega+1)$ and the last division is ultimately
$$Y^2=\bigl(\omega(\omega+1)Y^2\bigr)\cdot(\omega+1).$$
To answer your last questions, $\deg ?_a=0$, and $\:?_b=0$
