Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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$.

share|cite|improve this answer
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
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. – Arturo Magidin Dec 30 '11 at 20:48
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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