# Division binary using polynomials

I want to do a division of two binaries and take the rest (mod). But I want to do this using polynomials, let's take the example:

binary dividend: 010001100101000000000000 binary divisor: 100000111

polynomial form dividend: x²²+x¹⁸+x¹⁷+x¹⁴+x¹²

polynomial form divisor: x⁸+x²+x¹+x⁰

after the division: x²²+x¹⁸+x¹⁷+x¹⁴+x¹² / x⁸+x²+x¹+x⁰

result is: x¹⁴+x¹⁰+x⁹+x⁸+x⁷+x²+x¹

Remainder is : x⁷+x⁴+x¹

Someone can explain to me, step-by-step, how to do this division? Without convert to binary, needs to be in polynomial form.

Thank you.

## migrated from mathematica.stackexchange.comMay 2 '15 at 4:04

This question came from our site for users of Wolfram Mathematica.

• If you want to get the result by hand, you can do polynomial long division exactly like regular long division. – 2012rcampion May 2 '15 at 0:31
• @2012rcampion yes, I will make this question in that another one. Is a question about CRC, it's a computation method.. I will take a look in wolfram to understand better. Anyway, thank you. – Johnny Willer May 2 '15 at 0:42

PolynomialQuotientRemainder[x^22+x^18+x^17+x^14+x^12,x^8+x^2+x+1,x,Modulus->2]

{x+x^2+x^7+x^8+x^9+x^10+x^14,x+x^4+x^7}


Update for move to math:

Well, now that it's here, the Mathematica answer doesn't seem quite as useful anymore.

The answer is that you use the same long division you learned in elementary school. The only difference is that now you do it all modulo 2, so $1+1=0$. Similarly $x^2+x^2=0$. And consequently $-x^2=x^2$.

Then for:

$$x^3+x+1\over x+1$$

we start the long division by multiplying $x+1$ by $x^2$ so that we can get rid of the $x^3$ term. The first term in our quotient is then $x^2$. We get $x^3+x^2$. We now have:

$$x^2+{x^2+x+1\over x+1}$$

Doing that again, we get:

$$x^2+x+{1\over x+1}$$

The final term has a smaller degree over a larger degree, so we can proceed no further. The quotient is $x^2+x$ and the remainder is $1$.

• You can explain to me, how get this result? – Johnny Willer May 2 '15 at 0:20
• @JohnnyWiller you may be looking for the Mathematics Stack Exchange, rather than the Mathematica stack exchange, as indicated by 2012rcampion above. This SE is about a specific software package that is often used to do mathematics, not about mathematics in general. – evanb May 2 '15 at 0:32
• Ok, thank you for your help – Johnny Willer May 2 '15 at 0:42
• Great explanation. – MrZander Oct 20 '17 at 17:25