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
    Edited my original post. Think we've got the same result. So it's just important to keep in mind that theres only residue class 0 and 1 and hence $1+1=0$ and $1-1=0$. And then just proceed with the usual long polynomial division algorithm?2011-12-30
  • 0
    @meinzlein: Yes, the division algorithm works over any field (just keep in mind that you are doing the operations in the field; and in $\mathbf{F}_2$, the field with two elements, $a+a=0$ for all $a$), and as Bill Dubuque points out, in any commutative ring so long as the leading coefficient of the divisor is invertible (which happens automatically when the coefficients are in a field).2011-12-30
  • 0
    The Euclidian Algorithm to compute the GCD works then as usual as well? I had two polynomials in $\mathbb{Z}/2\mathbb{Z}$ and used the euclidian algorithm and got the same divisor several times which turned out to be the GCD at the end when I finally got remainder 0.2011-12-30
  • 0
    Yes, the Euclidean algorithm works too for polynomials over any field. Remember that the remainder must have degree *strictly smaller* than the divisor (you may have done the same mistake you did in this problem, where your "remainder" was not really the remainder because the degree was equal). The Euclidean algorithm works, mutatis mutandis, as with integers. The last nonzero remainder is a gcd.2011-12-30
  • 0
    I used the Euclidian algorithm to compute the GCD of $x^5 + x^4 + 1$ and $x^4 + x^2 + 1$. For the first division I've got divisor $x$ and remainder $x^4 + x^3 + x + 1$. So I went on and divided the second polynomial by the remainder ... aso ... got divisor $1$ and $x$ again and again and in the end I've got remainder $x$ and the GCD $x^2 + x + 1$.2011-12-30
  • 0
    @meinzlein: As I surmised, you are doing the division wrong. The remainder when dividing by $x^4+x^2+1$ **cannot** be $x^4+x^3+x+1$, because the degree of the latter is *equal* to the degree of the divisor. The remainder must be of *strictly smaller* degree. Exactly the same mistake you made in the posted problem. You can still divide $x^4+x^3+x+1$ by $x^4+x^2+1$ to get a quotient of $1$ and a remainder of $x^3+x^2+x$.2011-12-30
  • 0
    Oh what a mistake - got confused. So I've got the first step: $(x^5 + x^4 +1) : (x^4 + x^2 + 1) = (x+1)$ an remainder $(x^3 + x)$. Then in the second step: $(x^4 + x^2 + 1) : (x^3 + x) = x$ and remainder $1$. Then the last would be $(x^3 + x) : 1 = (x^3 + x)$ with remainder $0$. Is now $1$ or $(x^3 + x)$ the GCD?2011-12-30
  • 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