# Why $x^{p^n}-x+1$ is irreducible in ${\mathbb{F}_p}$ only when $n=1$ or $n=p=2$

I have a question, I think it concerns with field theory.

Why the polynomial $$x^{p^n}-x+1$$ is irreducible in ${\mathbb{F}_p}$ only when $n=1$ or $n=p=2$?

Thanks in advance. It bothers me for several days.

-
Is this a typo: "only when n=1 of n=p=2"? I guess you mean "or". –  user2468 Mar 19 '12 at 22:38
Also. When $n = 1,$ and since $x^p \equiv x \pmod p$ by FLT, we have $x^{p^n} - x +1 \equiv 1 \pmod p.$ –  user2468 Mar 19 '12 at 22:41
Sorry, it's "only when n=1 or n=p=2." And J.D., FLT only shows that this polynomial has no linear factors when n=1. –  Ken How Mar 19 '12 at 22:48
@JD x is not in $\mathbb F_p$. The polynomial $x^p-x$ is not zero, it just has roots in $\mathbb F_p$. –  Thomas Andrews Mar 19 '12 at 23:06
If $p$ does not divide $n$, then the polynomial is divisible by $x^p-x+1/n$. I don't immediately see why $x^{p^p}-x^p+1$ couldn't be irreducible, though. –  David Speyer Mar 19 '12 at 23:28

We will use fairly liberally the result that if $q(x)\in\mathbb F_p[x]$ is irreducible, then, for any $k$, $q(x)\mid x^{p^k}-x$ if and only if $\deg q\mid k$.

If $q_n(x)=x^{p^n}-x+1$ is irreducible, then there is a automorphism, $\phi$ of the field $\mathbb F_p[x]/\left<q_n(x)\right>$ which sends $\bar x$ to $\bar x-1$, namely:

$$\phi(\alpha)=\alpha^{p^n}$$

for any element $\alpha$. (Where $\bar x$ is the image of $x$ from $\mathbb F_p[x]$ in this field.)

Then, $\phi(\bar x)=\bar x^{p^n}=\bar x-1$. So that automorphism must have order $p$: $\phi^p = 1$, the identity automorphism.

Now, $\phi^k(\alpha)=\alpha^{p^{kn}}$, so, in particular, $\bar x=\phi^p(\bar x)=\bar x^{p^{pn}}$, and therefore we know $0=\bar x^{p^{pn}}-\bar x$, and therefore that the polynomial $x^{p^{pn}}-x$ is divisible by $q_n(x)$.

Using the result above, we therefore see that $p^n=\deg q_n(x)\mid pn$. But $p^n\mid pn$ can only happen if $n=1$ or $n=2$ and $p=2$.

I think you can show that $q_1(x)\mid x^{p^p}-x$ pretty straight-forwardly, therefore showing that it must factor as elements of degree $p$ and degree $1$. But clearly it has no factors of degree $1$ since it has no roots in $\mathbb F_p$, so, since $\deg q_n=p$, $q_1(x)$ must be prime.

Then you have the last case, $x^4-x+1$ over $\mathbb F_2$, which you can brute force.

-
If $n=1$, then this argument shows that any irreducible factor has degree dividing $p$. But by Fermat's theorem there are no linear factors. For $n=p=2$, again there are no linear factors, and the only irreducible quadratic mod $2$ is $x^2+x+1$, which is also not a factor. –  Chris Eagle Mar 19 '12 at 23:08
Dear Thomas, your answer is quite difficult to read because your $x$ refers both to an indeterminate and a generator of a finite field. Also, polynomials have degrees, not dimensions. –  Georges Elencwajg Mar 19 '12 at 23:23
I never once talk about a generator of the field. @GeorgesElencwajg. Not sure if I mis-wrote dimension before, but somewhere in my edits, I managed to remove the word. I have fixed it so that $\bar x$ is used in the field as the image of $x$ in the polynomial ring, for some clarity. –  Thomas Andrews Mar 19 '12 at 23:32
Dear Thomas, I meant that $\bar x$ , your old $x$, was a generator of the field $\mathbb F_p[x]/\left<q_n(x)\right>$ i.e. that that field can be written $\mathbb F_p[\bar x]$. But notations are perfectly clear now and we can see how nice your proof is ! –  Georges Elencwajg Mar 19 '12 at 23:43
Ah, I thought you meant multiplicative generator of the units of the field, not algebraic generator. @GeorgesElencwajg –  Thomas Andrews Mar 19 '12 at 23:45