# Evaluation of the $\gcd (x^2-x+1, x^3+2x+2)$ in $\mathbb{Z_3}[x]$

The ring is $\mathbb{Z_3}[x]$. I am trying to find the $\gcd (x^2-x+1, x^3+2x+2)$. So, $a_1 = x^3+2x+2 \in \mathbb{Z_3}[x]$ and $a_2 = x^2-x+1 \in \mathbb{Z_3}[x]$. By Euclidean algorithm for $a_1 = a_2 \times q_1 + a_3$, I am getting $q_1=x+1$ and $a_3=2x$. Then for $a_2 = a_3 \times q_2 + a_4$, I am getting $q_2=2x+1$ and $a_4=1$ (I used $x=4x$ in $\mathbb{Z_3}[x]$). Then for $a_3 = a_4 \times q_3 + a_5$, I am getting $q_3=2x$ and $a_5=0$. So $a_4=1 = \gcd (x^2-x+1, x^3+2x+2)$. On the other hand, $a_2=x^2-x+1 =(2x+2)^2$ and $a_1=x(2x+2)^2+2x+2$ so $\gcd (x^2-x+1, x^3+2x+2)$ must be $2x+2$ which is not equal to $1$ in $\mathbb{Z_3}[x]$. (!)

• Cubic polynomial is irreducible and quadratic polynomial doesn't divide the cubic polynomial. So gcd must be 1 – jnyan Nov 4 '16 at 4:19
• @jnyan, whatever I've written after "on the other hand," in the OP is the book's claim (adkins' algebra). But it seems to be correct. How it is not correct? – L.G. Nov 4 '16 at 4:22

$a_1$ from the book is: $a_1=x(2x+2)^2+2x+2=x^3-x^2+x+2x+2=x^3-x^2+2=x^3+2x^2+2$
While your $a_1$ is $x^3+2x+2$
• $a_1(2)= 2\, \, a_2(2)= 0,$, $2x+2$ gives 0. That would mean 0 is a divisor of 2. – jnyan Nov 4 '16 at 5:03
• You are working with one $a_1$ and by expanding the factorization in canonical form you get a different $a_1$. That is the problem. If you use the same $a_1$ and calculate $\gcd (x^2-x+1, x^3+2x^2+2)$ you will probably get $2x+2$. I don't know whether it's your mistake or it's written wrongly in the book. – Momo Nov 4 '16 at 5:05
• In short, you get different results because $x^3+2x+2\ne x(2x+2)^2+2x+2$. I hope you understand this time. – Momo Nov 4 '16 at 5:10
• The book has written $x^3+2x+2 = x(2x+2)^2+2x+2$. So mistake is the book's. So the gcd is 1, as I calculated? – L.G. Nov 4 '16 at 7:00