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

## Homework Statement

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)

## 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.

Hurkyl
Staff Emeritus
Gold Member
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 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.

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.

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.

Hurkyl
Staff Emeritus
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).

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).

So, how does that help?

Hurkyl
Staff Emeritus
Gold Member
Well, if I'm right, then your observation applies. Surely that's better than your observation not applying?

Well, if I'm right, then your observation applies. Surely that's better than your observation not applying?

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

$$f(x)=\prod_{j=0}^{p-1}(x-(b+j))$$.

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

$$g(x)=\prod_{j\in I}(x-(b+j))$$.

How does it follow that f has a root in F. Namely, that b is in F?