1

I am asked to find the gcd of $x^4 + 2x^3 + x + 1$ and $x^5 + 2x^3 + x^2 + x + 1$ in $F_3[x]$ (polynomials in $\mathbb Z/3\mathbb Z)$.

Using Euclid's Algorithm, I first divided $x^4 + 2x^3 + x + 1$ into $x^5 + 2x^3 + x^2 + x + 1$ to get $x + 1$ remainder $2x$. I then divided $2x$ into $x^4 + 2x^3 + x + 1$ to get $2x^3 + x^2 + 2$, remainder $1$, indicating that the gcd is 1. However, in the back of the text, the answer is that the gcd is $x^2 + 1$. Is there something here that I'm not understanding correctly? I've looked over the actual long division multiple times and I can't spot an error.

Brandon
  • 465
  • 4
  • 15
  • Dividing $x^5+2x^3+x^2+x+1$ by $x^4+2x^3+x+1$ yields a remainder of $6x^3+2x+3$. Check your calculations again. – Servaes Apr 09 '14 at 06:15
  • 1
    In $F_3$, is this not equal to $2x$? – Brandon Apr 09 '14 at 06:19
  • 1
    Ah, I overlooked that we're working over $\Bbb{F}_3$. Then indeed the $\gcd$ is $1$. – Servaes Apr 09 '14 at 06:27
  • The gcd is $,x^2+1,$ if the first ends $,\ldots \color{#c00}-x\color{#c00}-1,$ vs $,x+1.$ There are no single term sign changes that cause the first to be divisible by $,x^2+1.\ \ $ – Bill Dubuque Apr 09 '14 at 15:25

0 Answers0