Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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?

share|cite|improve this question

marked as duplicate by Martin Sleziak, Amzoti, Micah, J. M., Shuhao Cao Jun 1 '13 at 5:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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
up vote 7 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer

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

share|cite|improve this answer
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)$.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.