1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook