<s>[INST] GCD of polynomials in $\mathbb Z_5$ 
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$.
 [/INST] 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.
</s>