Find the gcd of ($x^2 + 1, x^3 + x +1)$ in $\mathbb{Z}_3[x]$

Question

Find the gcd of ($x^2 + 1, x^3 + x +1)$ in $\mathbb{Z}_3[x]$

I have no idea how to do this really. Any help is appreciated. Here is my attempt:

$x^3 + x + 1$ = $x(x^2 + 1) + 1$

$x^2 + 1 = (x^2)(1) + 1$

In particular I am confused about how I am supposed to find the gcd in the field $\mathbb{Z}_3$? Thanks.

Answer 1

Since $x^3+x+1=x(x^2+1)+1$, using the Euclidean Algorithm, we find:

$$\text{gcd}(x^3+x+1, x^2+1)=\text{gcd}(x^2+1, x^3+x+1-x(x^2+1))=\text{gcd}(x^2+1, 1)=1$$