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]$. (!)

How the contradiction happens?

  • $\begingroup$ Cubic polynomial is irreducible and quadratic polynomial doesn't divide the cubic polynomial. So gcd must be 1 $\endgroup$ – jnyan Nov 4 '16 at 4:19
  • $\begingroup$ @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? $\endgroup$ – 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$

So they are different polynomials.

  • $\begingroup$ But still I cant understand why do I have to ignore 2x+2 as the common factor of the both a_1 and a_2? thanks $\endgroup$ – L.G. Nov 4 '16 at 4:57
  • $\begingroup$ $a_1(2)= 2\, \, a_2(2)= 0, $, $2x+2$ gives 0. That would mean 0 is a divisor of 2. $\endgroup$ – jnyan Nov 4 '16 at 5:03
  • $\begingroup$ 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. $\endgroup$ – Momo Nov 4 '16 at 5:05
  • $\begingroup$ In short, you get different results because $x^3+2x+2\ne x(2x+2)^2+2x+2$. I hope you understand this time. $\endgroup$ – Momo Nov 4 '16 at 5:10
  • $\begingroup$ 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? $\endgroup$ – L.G. Nov 4 '16 at 7:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.