69
$\begingroup$

Let $p$ be a prime. How do I prove that $x^p-x+a$ is irreducible in a field with $p$ elements when $a\neq 0$?

Right now I'm able to prove that it has no roots and that it is separable, but I have not a clue as to how to prove it is irreducible. Any ideas?

  • 1
    When reading recently an article about the Artin-Schreier theorem, some properties of the so-called *Artin extensions* were used, and, if no mistakes occur here, those are intimately related to the polynomials of the form $x^p-x+a$. Is there indeed any error that occur? and is there any reference to know more in this direction? Thanks in advance.2011-11-13
  • 1
    @awllower: [This question](http://math.stackexchange.com/q/50041/11619) may get you started?2011-11-13
  • 0
    @JyrkiLahtonen: Thanks for the question. I really appreciate this.2011-11-13
  • 1
    The original version of the question (which I've now edited) omitted the requirement that $p$ be a prime. This requirement was necessary: The polynomial $x^4-x+a$ over $\mathbb{F}_4$ is reducible for every $a \in \mathbb{F}_4$ !2016-09-18
  • 0
    This is also a particular case of http://math.stackexchange.com/questions/136164 .2016-09-18

7 Answers 7

1

The supposition of Greg Martin is truth, if a polinomyal $f$ with $deg(f)=n$ satisfies the property, then $n\ge p$, by contradiction argument, just write the expansion with the Newton's formula and analyse the coeficient of $x^{n-1}$ term, you get $\binom n 1a_{n}+a_{n-1}=a_{n-1}$, if $n\lt p$, this equation is an absurd.

60

$x \to x^p$ is an automorphism sending $r$ to $r-a$ for any root $r$ of the polynomial. This operation is cyclic of order $p$, so that one can get from any root to any other by applying the automorphism several times. The Galois group thus acts transitively on the roots, which is equivalent to irreducibility.

  • 6
    Impressively elegant, zyx: +12013-07-24
55

Greg Martin and zyx have given you IMHO very good answers, but they rely on a few basic facts from Galois theory and/or group actions. Here is a more elementary but also a longer approach.

Because we are in a field with $p$ elements, we know that $p$ is the characteristic of our field. Hence, the polynomial $g(x)=x^p-x$ has the property $$g(x_1+x_2)=g(x_1)+g(x_2)$$ whenever $x_1$ and $x_2$ are two elements of an extension field of $\mathbb{F}_p$. By little Fermat we know that $g(k)=k^p-k=0$ for all $k\in \Bbb{F}_p$. Therefore, if $r$ is one of the roots of $f(x)=x^p-x+a$, then $$f(r+k)=g(r+k)+a=g(r)+g(k)+a=f(r)+g(k)=0,$$ so all the elements $r+k$ with $k \in \Bbb{F}_p$ are roots of $f(x)$, and as there are $p$ of them, they must be all the roots. It sounds like you have already shown that $r$ cannot be an element of $\Bbb{F}_p$.

Now assume that $f(x)=f_1(x)f_2(x)$, where both factors $f_1(x),f_2(x)\in \Bbb{F}_p[x]$. From the above consideration we can deduce that $$ f_1(x)=\prod_{k\in S}(x-(r+k)), $$ where $S$ is some subset of the field $\Bbb{F}_p$. Write $\ell=|S|=\deg f_1(x)$. Expanding the product we see that $$ f_1(x)=x^\ell-x^{\ell-1}\sum_{k\in S}(r+k)+\text{lower degree terms}. $$ This polynomial was assumed to have coefficients in the field $\Bbb{F}_p$. From the above expansion we read that the coefficient of degree $\ell-1$ is $|S|\cdot r+\sum_{k\in S}k$. This is an element of $\Bbb{F}_p$, if and only if the term $|S|\cdot r\in\Bbb{F}_p$. Because $r\notin \Bbb{F}_p$, this can only happen if $|S|\cdot1_{\Bbb{F}_p}=0_{\Bbb{F}_p}$. In other words $f_1(x)$ must be either of degree zero or of degree $p$.

  • 1
    Well done, it is a good proof.2011-11-13
  • 0
    I love your proof. One thing is bothering me, though. And It's probably really obvious. How do you know that if $|S|\cdot r\in F_p$, then $|S|$ must be a multiple of $p$ in order for $|S|\cdot r$ to be in $F_p$? I know it has to do with the fact that $r\notin F_p$, and I have some intuition for it, but I don't know how to prove it.2011-11-14
  • 0
    @MathMastersStudent: If $|S|$ is not a multiple of $p$, then $|S|\cdot 1$ is an invertible element of $F_p$. So if $|S|\cdot r= b$ with $b\in F_p$, then $r=b|S|^{-1}$ would be in the prime field $F_p$ as well contradicting known facts.2011-11-14
  • 5
    Great answer as usual, Jyrki: +1. Just to show you how pathologically nit-picking some guys are, I would write $|S|\cdot 1_{F_p}=0_{F_p}$ rather than $|S|=0_{F_p}$, since $S$ is an integer and the integers are not included in a finite field...2013-07-24
  • 2
    This argument also applies to any field of characteritic $p$.2014-12-31
  • 0
    @Lao-tzu: Correct. Provided that the polynomial $x^p-x-a$ has no zeros in the said field. When we are looking at it over the prime field this happens, iff $a\neq0$. For other fields of characteristic $p$ it is more complicated.2014-12-31
  • 0
    @Jyrki Lahtonen: Yes, that's what I mean (I should have written as you did).2014-12-31
  • 0
    I thought so, @Lao-tzu. Added the remark just in case a future visitor starts wondering :-)2014-12-31
  • 0
    Good proof, Sir !2015-06-17
35

$f(x)$ is separable since its derivative is $f'(x) = -1 \ne 0$.

Suppose $\theta$ is a root of $f(x) = x^p - x + a$. Using the Frobenius automorphism, we have: \begin{align} f(\theta + 1) &= (\theta + 1)^p - (\theta + 1) + a\\ &= \theta^p + 1^p - \theta - 1 + a\\ &= \theta^p - \theta + a\\ &= f(\theta) = 0 \end{align}

Thus, by induction, if $\theta$ is a root of $f(x)$, then $\theta + j$ is also a root for all $j \in \mathbb F_p$.

By above, if $f(x)$ were to have a root in $\mathbb F_p$, then $0$ would a be a root too, but this contradicts $a \ne 0$. Thus, $f(x)$ has no roots in $\mathbb F_p$. (This can also be shown using Fermat's little theorem.)

Suppose $\theta$ is a root of $f(x)$ in some extension of $\mathbb F_p$. We know that $\theta + j$ is also a root for all $j \in \mathbb F_p$. Since $f(x)$ is of degree $p$, these are all of the roots of $f(x)$.

Clearly, $\mathbb F_p(\theta) = \mathbb F_p(\theta + j)$ for all $j \in \mathbb F_p$. Thus, all $\{\theta + j\}$ have the same degree over $\mathbb F_p$. Since $f(x)$ is separable, it follows that $f(x)$ must be the product of all minimal polynomials of $\{\theta + j\}$. Suppose the minimal polynomials have degree $m$. We have $p = km$ for some $k$. Since $p$ is prime, either $m = 1$; hence $\theta \in \mathbb F_p$, a contradiction. Or $k = 1$; hence $f(x)$ is irreducible because it's the minimal polynomial.

  • 0
    Ah, I already accepted it. I want to accept it another time but it will get as unaccepted :P Thank You for this wonderful proof :) :) :)2013-08-03
  • 0
    A good one! ${}$2013-08-03
  • 0
    Happy to help! I have it in my notes. I don't actually remember if I came up with it myself or found it somewhere.2013-08-03
  • 0
    What ever may be the source, Your Answer is good :)2013-08-03
16

I think the following idea works. Let $f(x) = x^p-x+a$. They key observation is that $f(x+1)=f(x)$ in the field of $p$ elements. Now factor $f(x) = g_1(x) \cdots g_k(x)$ as a product of irreducibles. Sending $x$ to $x+1$ must therefore permute the factors $\{ g_1(x), \dots, g_k(x) \}$. But sending $x$ to $x+1$ $p$ times in a row comes back to the original polynomial, so this permutation of the $k$ factors has order dividing $p$. It follows that either every $g_j(x)$ is fixed by sending $x$ to $x+1$ - which I think is a property that no nonconstant polynomial of degree less than $p$ can have, but that needs proof - or else there are $k=p$ factors, which can only happen in the case $a=0$.

  • 0
    This probably needs the separability of $f$, because if some of the $g_1,g_2,\ldots,g_k$ could be equal, the concept of a permutation and its order would be somewhat muddled.2016-09-18
11

$x^p-x+a$ divides $x^{p^p}-x$. If $f$ is an irreducible divisor of $x^p-x+a$ of degree $d$ then $\mathbf{Z}_p[x]/f$ will be a subfield of the field with $p^p$ elements so $p^p = (p^d)^e$ and so $d=1$ or $e=1$. since $x^p-x+a$ has no roots $e=p.$

8

One more proof, similar to Greg Martin's: Suppose $\alpha$ is a root of $f(x)=x^p-x+a$ in some splitting field; then \begin{equation*} (\alpha+1)^p - (\alpha+1) + a = \alpha^p + 1 - \alpha - 1 + a = \alpha^p - \alpha + a = 0, \end{equation*} so that $\alpha+1$ is also a root. It follows that the roots of $f$ are $\alpha+i$ for $0\le i < p$. If $f$ factors in $\mathbb{F}[x]$, say $f = gh$, then the sum of the roots of $g$ is $k\alpha + r$ where $\deg g = k$ and $k, r\in\mathbb{F}_P$. Since $g\in \mathbb{F}_p[x]$ it follows that $\alpha\in \mathbb{F}_p$. But that implies that $f$ splits in $\mathbb{F}_p$, which is not the case (for example, neither $0$ nor $1$ is a root). Thus $f$ is irreducible.

  • 0
    This is a very helpful and simple answer. Can I ask why it is not the case why f splits in Fp?2017-04-01
  • 0
    Also, by f splits in Fp, do you mean that Fp is the splitting field of f? Why would Fp being the splitting field of f imply that 0 or 1 is a root?2017-04-01
  • 0
    @P-S.D If $\alpha\in\mathbb{F}_p$, then the $p$ elements $\alpha+i$, $0\le i, are all in $\mathbb{F}_p$ and are all roots of $f$. But $f$ has degree $p$, so it clearly splits in $\mathbb{F}_p$ and thus each of the $p$ elements of that field, including $0$ and $1$, is a root of $f$.2017-04-02