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

Homework Help: GF(q); x^p-x+a has no root => irreducible [PROOF]

  1. May 22, 2010 #1

    UD1

    User Avatar

    1. The problem statement, all variables and given/known data

    Let q=p^e, where p is a prime and e is a positive integer. Let a be in GF(q). Show that f(x)=x^p-x+a is irreducible over GF(q) if and only if f(x) has no root in GF(q)

    2. Relevant equations



    3. The attempt at a solution

    One of the directions seems obvious. Namely, if f is irreducible, the f has no roots: if f had a root, say b in GF(q), then f(x)=(x-b)*g(x), where g is a poly with coefficients from GF(q).

    The other direction: if f has no root, then f is irreducible. Or equivalently, f is reducible, then f has a root in GF(q). Frankly, I don't have any ideas. The only "observation" I made is that if the power of f were q rather than p and it had a root, say b, then b+1, b+2,...,b+p-1 would be roots, too. I think the key point here is that I need to "guess" what the linear factorization of f in its splitting field looks like.
     
  2. jcsd
  3. May 22, 2010 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I could understand this if you were adding arbitrary elements of GF(q) -- but since you're just adding elements of GF(p), I don't understand why you are insisting on q instead of p.
     
  4. May 22, 2010 #3

    UD1

    User Avatar

    OK. It looks that there is some notation misunderstanding. I'm not that well familiar with finite fields so I might have used the type of notation not usually used.

    By GF(q) I mean a finite field of order q (with q elements) where q is a power of prime p, and that p is a characteristic of the field.
     
  5. May 22, 2010 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Right, that's what I thought you meant. The numbers you're adding to b: 0,1,2,...,p-1, are all elements of GF(p).
     
  6. May 22, 2010 #5

    UD1

    User Avatar


    So, how does that help?
     
  7. May 22, 2010 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, if I'm right, then your observation applies. Surely that's better than your observation not applying?
     
  8. May 22, 2010 #7

    UD1

    User Avatar

    So, we know that, assuming that b is a root in some extension of F, then

    [tex] f(x)=\prod_{j=0}^{p-1}(x-(b+j))[/tex].

    Now suppose that f is reducible, that is f=gh for some polynomials g and h whose coefficients are in GF(q). There must exists a proper subset I of {0,...,p-1} such that

    [tex] g(x)=\prod_{j\in I}(x-(b+j))[/tex].

    How does it follow that f has a root in F. Namely, that b is in F?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook