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

I am currently studying for an exam and trying to check a message (binary) for errors using a polynomial, I would like if somebody could verify that my results below are (in)valid.


Message: 11110101 11110101
Polynomial: X4 + x2 + 1
Divisor (Derived from polynomial): 10101
Result: There is an error in the above message?

Also, I had a link to an online calculator that would do the division but can't relocate it, any links to a calculator would be greatly appreciated.


share|cite|improve this question
up vote 2 down vote accepted
 1111010111110101 | 10101
+10101            | 11001011101
  10111           |
 +10101           |
     10011        |
    +10101        |
       11011      |
      +10101      |
        11101     |
       +10101     |
         10000    |
        +10101    |
           10110  |
          +10101  |
              111 | <- you are right! there is an error in the message!
share|cite|improve this answer

Mathematica gave me the same result:


In[2]:=PolynomialRemainder[(1+x^8)s, 1+x^2+x^4,x]

Out[2]:= 1+x+x^2

So there wasn't even any need to reduce the coefficients modulo two in the end. I don't know whether Wolfram Alpha supports this. Anyway, you got it right.

In this case we can also find non-divisibility by observing that $$ \begin{aligned}s&=x^7+x^6+x^5+x^4+x^2+1=(x^2+x+1)x^5+(x^2+x+1)^2\\ &=(x^2+x+1)(x^5+x^2+x+1)=(x^2+x+1)(x+1)^2(x^3+x+1)\end{aligned}$$ implying that your message polynomial $$ m=(x^8+1)s=(x^2+x+1)(x^3+x+1)(x+1)^{10} $$ is not divisible by $x^4+x^2+1=(x^2+x+1)^2$. In general trying to factor the message polynomial is a very bad idea, though :-)

share|cite|improve this answer

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.