# Irreducibility issue [duplicate]

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?

-

## marked as duplicate by Martin Sleziak, Amzoti, Micah, Ｊ. Ｍ., Shuhao CaoJun 1 '13 at 5:33

This is a standard application of Eisenstein. You don't apply the criterion to $f$ but rather to a polynomial related to $f$. –  Qiaochu Yuan Dec 23 '11 at 4:17
How is that polynomial related to $f$? –  yihangho Dec 23 '11 at 4:23
We've gotten this question at least once before, e.g. here (but in that instance there's no solution posted). –  Zev Chonoles Dec 23 '11 at 4:29
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$. –  Dylan Moreland Dec 23 '11 at 4:47
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. –  jspecter Dec 23 '11 at 4:50

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.

-
Do you mind to explain how the last congruence actually lead to the "idea" of applying Eisenstein's criterion on $f(x+1)$? –  yihangho Dec 23 '11 at 6:23
@yihan See also my answer, which elaborates a bit more on the motivation behind the problem-solving strategy. –  Bill Dubuque Dec 23 '11 at 15:35
@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. –  Qiaochu Yuan Dec 23 '11 at 18:40
@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$. –  yihangho Dec 24 '11 at 1:22
@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$. –  Qiaochu Yuan Dec 24 '11 at 1:46

HINT $\$ Eisenstein's Criterion applies to polynomials that have the form $\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.

-

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].$

-
I undeleted this because it is slightly different from Qiaochu's post. –  Geoff Robinson Dec 30 '11 at 16:22

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

-