# polynomial long division - coefficients in modulo 2 coset

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?

-
The high-school polynomial division algorithm obviously works over any coefficient ring, as long as the leading coefficient of the divisor is invertible. – Bill Dubuque Dec 30 '11 at 20:21

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$.
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? – meinzlein Dec 30 '11 at 20:26
@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). – Arturo Magidin Dec 30 '11 at 20:31
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. – meinzlein Dec 30 '11 at 20:46
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$. – meinzlein Dec 30 '11 at 20:56