7
$\begingroup$

This is a homework question.

Given $f(x)=x^{p-1}+x^{p-2}+\cdots+x+1$, where $p$ is any prime. Prove that $f(x)$ is irreducible over $\mathbb{Z}[x]$?

Any idea, hint, etc? Hint given by my book was to use Eisenstein's Irreducibility Criterion. But I see that the coefficients of each term is 1 which is not divisible by any prime number, so how can the criterion be satisfied?

  • 2
    This is a standard application of Eisenstein. You don't apply the criterion to $f$ but rather to a polynomial related to $f$.2011-12-23
  • 0
    How is that polynomial related to $f$?2011-12-23
  • 1
    We've gotten this question at least once before, e.g. [here](http://math.stackexchange.com/questions/87609/eisenstein-criterion-with-a-twist) (but in that instance there's no solution posted).2011-12-23
  • 1
    It might be helpful to notice that $$f(x) = \frac{x^p - 1}{x - 1}.$$ Remember that if the image of $f$ under some automorphism of $\mathbf Z[x]$ is irreducible then so is $f$.2011-12-23
  • 1
    I've always thought the application of Eisenstein's criterion in this case was a trick. I would love to see someone motivate it for a beginner.2011-12-23
  • 0
    @jspecter Well I took a stab at it below. Perhaps others can chime in (alas, my spare time is in short supply now).2011-12-23
  • 0
    See also [Irreducibility of $X^{p-1} + \ldots + X+1$](http://math.stackexchange.com/questions/215042/irreducibility-of-xp-1-ldots-x1)2013-06-01

4 Answers 4

8

As long as there's a complete answer, there might as well be a conceptual explanation too. As Dylan Moreland says in the comments, note that $f(x) = \frac{x^p - 1}{x - 1}$. Since $x^p - 1 \equiv (x - 1)^p \bmod p$ by Fermat's little theorem, it follows that $$f(x) \equiv \frac{(x - 1)^p}{x - 1} \equiv (x - 1)^{p-1} \bmod p$$

hence that $$f(x+1) \equiv x^{p-1} \bmod p.$$

But $f(1) = p$, so hopefully the idea of using Eisenstein's criterion on $f(x + 1)$ seems more natural now.

  • 0
    Do you mind to explain how the last congruence actually lead to the "idea" of applying Eisenstein's criterion on $f(x+1)$?2011-12-23
  • 0
    @yihan See also my answer, which elaborates a bit more on the motivation behind the problem-solving strategy.2011-12-23
  • 0
    @yihang: the last congruence shows that every coefficient except the leading one is divisible by $p$. If in addition the constant term is not divisible by $p^2$ then Eisenstein applies, and that's easy to check.2011-12-23
  • 0
    @QiaochuYuan Sorry I still cant get it. Can you please explain further? I can't see why the congruence shows that every coefficient expect the leading one is divisible by $p$.2011-12-24
  • 0
    @yihang: do you know what it means to say that two polynomials $f, g$ are congruent $\bmod p$? It means that every coefficient of $f - g$ is divisible by $p$. Now if $f(x + 1) \equiv x^{p-1} \bmod p$, that says precisely that the leading coefficient of $f(x + 1)$ is congruent to $1 \bmod p$ (in fact it's just $1$) and the others are divisible by $p$.2011-12-24
  • 0
    @QiaochuYuan Oh now I get it. Thanks a lot. The missing key was the congruent functions. Thanks again.2011-12-24
8

Hint $\ $ Eisenstein's Criterion applies to polynomials that are prime powers $\rm\ f\ \equiv\ x^n\pmod p.\:$ Though your polynomial $\rm\ f\ =\ (x^p-1)/(x-1)\ $ is not of that form, it is very close, namely $\rm\ f\ \equiv\ (x-1)^{p-1}\pmod{p}\:.\:$ Eisenstein's Criterion may apply if you can find a map $\ \sigma\ $ that sends $\rm\ (x-1)^{p-1}\ $ to a power of $\rm\ x\ $ and, further, $\ \sigma\ $ preserves factorizations $\rm\ \sigma(gh)\ =\ \sigma g\cdot \sigma h\ $ (so one can pullback the irreducibility of $\rm\ \sigma\:f\ $ to $\rm\:f).\:$ It suffices to find a find an automorphism $\:\sigma\:$ on $\rm\ \mathbb Z[x]\ $ that shifts $\rm\:x\!-\!1\to x\:.\ $ Any ideas?

The history of the criterion is very interesting (and quite instructive!) $\:$ See David A. Cox, Why Eisenstein proved the Eisenstein criterion and why Schönemann discovered it first.

Remark $\ $ This is prototypical of transformation-based problem solving. Consider the analogous case of solving quadratic equations. One knows how to solve the simple special case $\rm\ x^2 = a\ $ by taking square roots. To solve the general quadratic we look for an invertible transformation that reduces the general quadratic to this special case. The solution, dubbed completing the square, is well-known. The problem-solving strategy above is completely analogous. We seek transformations that map polynomials into forms where Eisenstein's criterion applies. But we also require that the transformation preserve the innate structure of problem - here multiplicative structure (so that we may conclude with: $\rm\:\sigma\:f\:$ irreducible $\Rightarrow$ $\rm\:f\:$ irreducible).

Employing such transformation-based problem solving strategies has the great advantage that one can transform theorems, tests, criteria, etc, into a simple reduced or "normal" form that is easy to remember or apply, and then use the ambient symmetries or transformations to massage any given example to the required normal form. This strategy is ubiquitous throughout mathematics (and many other sciences). For numerous interesting examples see Zdzislaw A. Melzak's book Bypasses: a simple approach to complexity, 1983, which serves as an excellent companion to Polya's books on mathematical problem-solving.

For another example, see the shift-based proof of the Factor Theorem in my REMARK here.

3

As a matter of interest I think you can do this problem without using Eisenstein if you accept the uniqueness of factorization in $F[x],$ where $F$ is the field with $p$ elements.For, as others have already remarked, we have $x^p - 1 = (x-1)^p$ and $1+x \ldots + x^{p-1} = (x-1)^{p-1}$ in $F[x].$ This means that if we can write $1+x \ldots + x^{p-1} = f(x).g(x)$ with $f(x),g(x) \in \mathbb{Z}[x],$ each of degree at least $1,$ then we have $f(x) = (x-1)^j + p.h(x)$ and $g(x) = (x-1)^{p-1-j} + p.k(x)$ for some integer $j$ with $1\leq j \leq p-1$ and polynomials $h(x),k(x) \in \mathbb{Z}[x].$ But notice then that $f(1)$ is an integer multiple of $p$ and $g(1)$ is an integer multiple of $p.$ However, evaluating $1 + x + \ldots + x^{p-1}$ at $1$ gives $p$, which is certainly not an integer multiple of $p^2.$ I remark, since it has been mentioned in another problem about $p$-power cyclotomic polynomials on this site, that this method also works for the cyclotomic polynomial $\Phi_{p^k}(x)$ for any positive integer $k,$ since we have $\Phi_{p^k}(1) = p$ and the image of $\Phi_{p^k}(x)$ factors as $(x-1)^{\phi(p^k)}$ in $F[x].$

  • 0
    I undeleted this because it is slightly different from Qiaochu's post.2011-12-30
2

Note that if $f(x)=x^{p-1}+x^{p-2}+\cdots+x+1$, then $f(x+1)=(x+1)^{p-1}+(x+1)^{p-2}+\cdots+(x+1)+1$. Then the coefficient $a_k$ of $x^k$ is given by $${p-1\choose k}+{p-2\choose k}+\cdots+{k\choose k}={p \choose k+1},$$ where the last equality follows from equation 10 in here. Therefore, $a_k$ is divisible by $p$ for $k=0,...,p-2$, $a_{p-1}=1$ is not divisible by $p$, and $a_0=p$ is not divisible by $p^2$. Therefore by Eisenstein's criterion, $f(x+1)$ is not irreducible. This implies that $f(x)$ cannot be irreducible; otherwise, if $f(x)=g(x)h(x)$, $f(x+1)=g(x+1)h(x+1)$.