GCD of polynomials in $\mathbb Z_5$

Question

I have to find the $\gcd(p(x),h(x))$ where $p(x)=1+2x+x^2+3x^3$ and $h(x)=2+x+x^5+x^6$ are in $\mathbb Z_5$.

To find the solution, I divide $h(x)/p(x)$ and I get $q_1(x)=2x^3+3x^2-1$ and $r_1(x)=3x^2+3x+3$

Should I divide $p(x)/r_1(x)$ ?

I think $r_1(x)$ is irreducible but I don't know what to conclude from this .

Also the answer of the exercise is $\gcd(p(x),h(x))=2$ but I don't know how to get $2$.

Answer 1

The GCD doesn't change if you multiply $p$ by $2$, so to get $$ 2+4x+2x^2+x^3 \qquad\text{and}\qquad 2+x+x^5+x^6 $$ The first remainder is $3x^2+x$, but we can multiply it by $2$: $$ 2x+x^2 \qquad\text{and}\qquad 2+4x+2x^2+x^3 $$ The remainder is $4x+2$, but we can multiply it by $4$: $$ x+3 \qquad\text{and}\qquad 2x+x^2 $$ The remainder is $3$.

Thus the two polynomials are coprime. Answering $3$, $2$ or $1$ for the GCD is the same, as it is determined up to an invertible element.