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

Polynomials/ galois field question

  1. Dec 18, 2007 #1
    [SOLVED] polynomials/ galois field question

    Im reading through a section that deals with polynomials Galois fields and ran into something that Im not quite understanding.

    Say we have an irreducible polynomial, f(x), which has coefficients from GF(2) and roots
    [tex]\beta[/tex], [tex]\beta[/tex][tex]^{2}[/tex], [tex]\beta[/tex][tex]^{4}[/tex], [tex]\beta[/tex][tex]^{8}[/tex], .........[tex]\beta[/tex][tex]^{2}[/tex][tex]^{e}[/tex][tex]-1[/tex] where e is the smallest integer such that [tex]\beta[/tex][tex]^{2}[/tex][tex]^{e}[/tex] = [tex]\beta[/tex]

    given by

    f(x) = [tex]\prod[/tex][tex]^{e-1}_{i=0}[/tex] ( X + [tex]\beta[/tex][tex]^{2^i}[/tex])

    Note: Beta term is Beta^(2^i)

    In the section Im reading, they do a test to prove f(x) is irreducible. I will state the test below

    Say f(x) = a(x).b(x) where a(x) and b(x) are polynomials with coefficients from GF(2)

    if we sub one of the roots of f(x) in, say [tex]\beta[/tex], f([tex]\beta[/tex]) = 0 which means that either a([tex]\beta[/tex]) = 0 or b([tex]\beta[/tex]) = 0, hence a(x) = f(x) or b(x) = f(x). This understanding also says that a(x) or b(x) (depending which one had [tex]\beta[/tex] subbed into it) has all the roots of f(x) (A theory in my textbook says that if f([tex]\beta[/tex]) = 0, f([tex]\beta[/tex][tex]^{2^i}[/tex])=0 for any i)

    I get how they arrive at their result, however Im still clueless as to how this proves that
    f(x) is irreducible.

    insight is appreciated

    Last edited: Dec 18, 2007
  2. jcsd
  3. Dec 18, 2007 #2
    Ok I read over the notes again and think I may have the answer

    Since f(x) = a(x) or f(x) = b(x) when the root is substituted in, it cannot be divided into a smaller polynomial with a non-zero degree. Therefore f(x) must be irreducible.

    Thoughts, comments, insights ??
  4. Dec 18, 2007 #3


    User Avatar
    Science Advisor
    Homework Helper

    I'm confused. You start out by saying that f(x) is irreducible, presumably over GF(2). Then you go on to prove that f(x) is irreducible - this time over what?

    Also, why is this in the Set Theory, Logic, Probability, Statistics forum? It really should be in the algebra forum.
  5. Dec 19, 2007 #4
    I answered my own question (see f(x)=a(x).b(x) proof), it was just that I didn't read over the notes properly.

    Sorry about the confusion

    Also, someone pls move this topic to the correct forum. ta
    Last edited: Dec 19, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook