Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Coding and GF(2)

  1. Nov 26, 2007 #1


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    This came up in my logic course.

    The professor writes that in GF(2), the polynomials [tex]3xy^5[/tex] and [tex]\frac{1}{2}x^2y[/tex] respectively can be reduced to [tex]3xy[/tex] and [tex]xy[/tex].

    I understand that [tex]y^5=(y^2)(y^2)y=(1)(1)y=y[/tex], but also in GF(2), for any x, we have x+x=0. So it seems to me that [tex]3xy^5[/tex] can be further reduced to just [tex]xy[/tex] because we have [tex]3xy=xy+xy+xy=0+xy=xy[/tex].

    For the other, I am clueless. Sure, [tex]x^2y=xy[/tex] because in GF(2), for any x, we have x²=x. But what happened to the 1/2? Worse, what is 1/2? It's the inverse of 2. And 2 is 1+1. But 1+1=0, and 0 has no inverse in a field.

    What's going on here?
  2. jcsd
  3. Nov 26, 2007 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    First off, just to make sure it's clear, we're talking about polynomial functions, not polynomials. The distinction is subtle, yet vital.

    Secondly, [itex]x^2 \not\equiv 1[/itex]; I'm not sure where you got that idea. The right fact is [itex]x^2 \equiv x[/itex].

    Thirdly, 1/2 doesn't make any sense in GF(2), because as you say, it's equivalent to 1/0.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook