0
$\begingroup$

What's important when dividing the following two polynomials

$x^4 + x + 1 \qquad \;\;\,\in \mathbb{Z}/2\mathbb{Z}[x]$

$x^3 - x^2 + 1 \qquad \in \mathbb{Z}/2\mathbb{Z}[x]$

How two calculate the first step

$\quad\,(x^4 + x + 1) : (x^3 - x^2 + 1) = x + 1 \; ...$

$-(x^4 -x^3 + x)$


$\quad \;\;\;x^3 + 1 \qquad \text{is this right?}$

$-(x^3 - x^2 + 1)$


$\quad \;\;\;x^2 \qquad \text{is this right?}$

So $x^4-x^4=0$ and since its residue class $x^4+x^4=0$ as well?

  • 1
    The high-school [polynomial division algorithm](http://en.wikipedia.org/wiki/Polynomial_long_division) obviously works over any coefficient ring, as long as the leading coefficient of the divisor is invertible.2011-12-30

1 Answers 1

1

You do long division with coefficients in $\mathbb{Z}/2\mathbb{Z}$ exactly the same way as you do coefficients in $\mathbb{Z}$ (or $\mathbb{Q}$); just remember that $1=-1$.

So $x(x^3-x^2+1) = x(x^3+x^2+1) = x^4 + x^3 + x$, hence $x^4 + x + 1 - x(x^3+x^2+1) = x^4+x+1+x^4+x^3+x = x^3+1.$ However, you are not done dividing, since you can divide $x^3+1$ by $x^3+x^2+1$: $x^3+1 = 1(x^3+x^2+1) + x^2.$ So the correct remainder is $x^2$, not $x^3+1$. The expression is $x^4 + x + 1 = (x+1)(x^3+x^2+1) + x^2,$ so the quotient is $x+1$ and the remainder is $x^2$.

  • 0
    @meinzlein: Just as in the Euclidean algorithm, *a* GCD is the last **nonzero** remainder. The last nonzero remainder here is $1$, so that means that $x^5+x^4+1$ and $x^4+x^2+1$ have $1$ as$a$GCD.2011-12-30