0

Here is the problem:

R=GF(2)[x]  mod  x^3 + 1 = 0

Now, I know these are the 8 elements in it.

0, 1, x, x+1, x2, x2 + 1, x2 + x, x2 + x + 1

According to the question I asked here: Constructing add/multi tables for GF(2)

The 8 elements come from any element in GF(2)[x] divided by x^3 + 1. Then there are 8 possible remainders, and those remainders are the 8 elements.

I don't understand this though. If 0 is an element, and I divide that by x^3 + 1, I get 0 as an answer, with no remainder. Where are these 8 remainders coming from? Does the amount of remainders change if instead of x^3 + 1, it was x^4 + 1, or x^3 + x + 1?

Community
  • 1
pfinferno
  • 307

1 Answers1

1

‘No remainder’ means a remainder equal to $0$.

The remainders are all the polynomials of degree at most $2$ in $\mathbf F_2[x]$: $$\{0,1,x, x^2, 1+x, 1+x^2, x+x^2,1+x+x^2\}.$$

For $x^3+x+1$ it would be the same, but the Cayley tables for multiplication would be different.

For $x^4+1$ as well as for $x^3+1$, you don't obtain a field, because the polynomials are not irreducible, as pointed @fkraiem 4: $$x^4+1=(x^2+1)^2,\quad x^3+1=(x+1)(x^2+x+1).$$

Bernard
  • 175,478
  • Oh, so why are they called remainders then? What is being divided to get those remainders? – pfinferno Sep 13 '15 at 23:06
  • You take every polynomial in $GF(2)[x]$, and try dividing it by $x^3 + 1$. Even though you're trying infinitely many dividends, you end up with only $8$ distinct remainders. – Henry Swanson Sep 13 '15 at 23:08
  • @pfinferno: it is like congruence classes in $\mathbf Z$. You partition the set of polynomials into $8$ classes, according to their remainder upon division by $x^3+1$. – Bernard Sep 13 '15 at 23:12
  • $x^3+1 = (x^2-x+1)(x+1)$ is not irreducible over $\mathbf{F}_2$ either (or indeed over any field). ;) – fkraiem Sep 13 '15 at 23:12
  • Oops! What a stupid mistake! I'll correct that at once. Thank you for pointing it. – Bernard Sep 13 '15 at 23:14
  • Okay that makes sense now! One question though, I can still make an addition/multiplication table for x^3 + 1 and x^4 + 1? Why isn't x^3 + 1 reducible over any field? – pfinferno Sep 13 '15 at 23:47
  • Oh wait, they have to be irreducible for it? – pfinferno Sep 13 '15 at 23:54
  • You'all always have a multiplication table, but you obtain a field only if the polynomial is irreducible. As pointed by @frkaiem $x^3+1$ is reducible over any field. – Bernard Sep 14 '15 at 00:24
  • I have a question that says to construct the addition and multiplication tables for those 3 rings. So those 8 elements wouldn't work for x^4 +1 and x^3 + 1? (Can take this to discussion if you want). I see that they aren't irreducible, but don't know what why that is important regarding construction of those tables. – pfinferno Sep 14 '15 at 00:55
  • Whether irreducible or not is unimportant for the tables construction. The $8$ elements work for all polynomials of degree $3$, but the products will not be the same. As for $x^4+1$, you will need the $16$ polynomials of degree $<4$. – Bernard Sep 14 '15 at 07:49
  • Oh I see now, that makes sense. Thank you very much. – pfinferno Sep 14 '15 at 14:30
  • Is "@fkraiem 4"denoting some variant of fkraiem ? Should it be "as pointed out by fkraiem ?" – Dietrich Burde Oct 01 '15 at 19:34