Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to prove that

$p(x):=x^n-x-1 \in \mathbb Q[x]$ for $n\ge 2$ is irreducible.

My attempt.

  1. GCD of coefficients is $1$, $\mathbb Q$ is the field of fractions of $\mathbb Z$, and $\mathbb Z$ is UFD. Hence, $p(x)$ is irreducible over $\mathbb Q$ iff it's irreducible over $\mathbb Z$ (Gauss's lemma).

  2. Let $m\in \mathbb Z$ such that $\varphi(m)=n$ (Euler's totient). Make reduction of $p(x)$ by modulo $m$. Because of $\overline{x^n}=\overline{x^{\varphi(m)}}=\overline{1}$, we get $\overline{p(x)}=\overline{1-x-1}=\overline{-x}$, which is irreducible. Hence, $p(x)$ is irreducible.

Does this proof is correct?

UPDATE. Thanks to Calvin Lin. My mistake is: not for all $n$ we can find such $m$. OK, but as for the rest, does my proof is correct for such $n$, that $n=\varphi(m)$ for an integer $m$? And can it be some changed for all $n$, i.e. can we find such modulo that $\overline{p(x)}$ is irreducible for every $n\ge 2$?

share|improve this question
How do you know that there is an $m$ such that $\phi(m) = n$? –  Calvin Lin May 16 '13 at 16:04
Just knowing $k^{\phi(m)}\equiv 1\pmod m$ for all $k\in\mathbb Z$ does not make the equality $x^{\phi(m)}=1$ hold in $\mathbb Z_m[x]$. –  Ted Shifrin May 16 '13 at 16:15
@Ted Shifrin: Why? –  Corvus May 16 '13 at 16:20
@user14284: the congruence $k^{\varphi(m)} \equiv 1 \bmod m$ is not true for all integers $k$, only those $k$ that are rel. prime to the modulus $m$, Your polynomial congruence $x^{\varphi(m)} \equiv 1 \bmod m{\mathbf Z}[x]$ is just false. Try it when $m = 3$: is $x^2 \equiv 1 \bmod 3{\mathbf Z}[x]$? Nope.... –  KCd May 16 '13 at 18:40
The point I was making is a rather subtle one, which students struggle with in abstract algebra. There is a big difference between $f(x)\in F[x]$ and $f(x)$ as a function that you'd study in calculus. For example, baby Fermat says that $f(x)=x^p-x\in(\mathbb Z/p\mathbb Z)[x]$ has the value $0$ when you evaluate it at every element of $\mathbb Z/p\mathbb Z$. Nevertheless, it is not the $0$-polynomial! –  Ted Shifrin May 19 '13 at 18:06

3 Answers 3

up vote 10 down vote accepted

I doubt an easy proof of the irreducibility exists in general. If $n$ is a prime, then the polynomial is Artin-Schreier and handled easily.

Selmer gave a clever proof in the general case, working explicitly with the roots of the polynomial in $\mathbb{C}$. See E. S. Selmer, On the irreducibility of certain trinomials, Math. Scand. 4 (1956), 287-302, available here.

share|improve this answer
Not only is the proof of irreducibility of $x^n-x-1$ over ${\mathbf Q}$ nontrivial, but Selmer points out in Section 6 of his paper that the method that he developed to prove irreducibility of these polynomials doesn't seem viable as an irreducibility test for other families of polynomials, aside from the one other family he considers in his paper. –  KCd May 16 '13 at 18:31
There is a paper from 1960 by Ljunggren with another approach to proving the irreducibility of these trinomials. See the answer to mathoverflow.net/questions/56579/about-irreducible-trinomials –  KCd Jun 20 '13 at 0:32
@KCd: That is interesting. Thanks! –  Brandon Carter Jun 20 '13 at 14:23
See my answer for a sketch of a proof that is easier to work through than Selmer's. –  KCd May 18 '14 at 21:46
@awllower: It's updated now. –  Brandon Carter Oct 30 '14 at 0:43

I will sketch a proof of the irreducibility of $x^n - x - 1$ over ${\mathbf Q}$ for $n \geq 2$ that is simpler than Selmer's argument. I learned of this approach from David Rohrlich, who learned it from Michael Filaseta.

Let $f(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$ be nonzero in $F[x]$ for any field $F$. Let $\tilde{f}(x) = x^{\deg f}f(1/x)$ be its reciprocal polynomial: $\tilde{f}(x) = a_0x^n + a_1x^{n-1} + \cdots + a_{n-1}x + a_n$. If $f(0) \not= 0$ then $f$ and $\tilde f$ have the same degree. Easily if $f = gh$ then $\tilde{f} = \tilde{g}\tilde{h}$, and $\widetilde{cf} = c\tilde{f}$ for any constant $c$.

In terms of factorization over roots, if $f(0) \not= 0$ then $$ f(x) = c(x-r_1)\cdots(x-r_n) \Longrightarrow \tilde{f}(x) = f(0)c(x - 1/r_1)\cdots(x-1/r_n). $$

Step 1: Let $f(x) \in {\mathbf Z}[x]$ satisfy (i) $f(0) \not= 0$ and (ii) $f(x)$ and $\tilde{f}(x)$ have no common roots. If $f(x) = g(x)h(x)$ for some nonconstant $g(x)$ and $h(x)$ in $\mathbf Z[x]$, show there is a $k(x)$ in $\mathbf Z[x]$ with $\deg k = \deg f$ such that $f\tilde{f} = k\tilde{k}$ and $k \not= \pm f$ or $\pm\tilde f$. If $f(x)$ is monic and $f(0) = \pm 1$, show you can take $k$ to be monic. (Hint: Use $k = \pm g\tilde{h}$ for a suitable choice of sign.)

Step 2: For $n \geq 2$, show the polynomial $x^n - x - 1$ doesn't have any roots in common with its reciprocal.

Step 3: Let $f(x) = x^n - x - 1$ for $n \geq 2$. Suppose $f\tilde{f} = k\tilde{k}$ for some monic $k \in \mathbf Z[x]$ of degree $n$. Compare the degree $n$ coefficients on both sides of the equation $f\tilde{f} = k\tilde{k}$ to show that $k$ must be a sum of 3 monomials whose coefficients are all $\pm 1$. Then look at the top 3 nonzero terms on both sides to show $k = f$ or $k = -\tilde{f}$.

Step 4: Combine all the previous steps to deduce irreducibility of $x^n - x - 1$ over $\mathbf Q$.

Exercise: Use the same argument to determine when $x^n + x + 1$, $x^n - x + 1$, and $x^n + x - 1$ are irreducible over $\mathbf Q$. (With a computer you can find in each case that there is a congruence condition on $n$ for it to be reducible, and this turns out to be exactly the condition for $f(x)$ and $\tilde{f}(x)$ to have a common root, which will be either a 3rd or 6th root of unity.)

share|improve this answer
This is outlandishly clever! Make sure it gets included into some textbook or lecture notes :-) –  fedja Jun 16 '14 at 3:56
Could the argument presented here be used to solve this problem as well ? –  Lucian Feb 7 at 14:51

Edit: There is a mistake in this proof. I think it can be fixed with an argument from the degrees of $q$ and $q'$, so I'll work on that.

Suppose $p(x)$ is reducible. Then $$ p(x) = (x^i + q(x))(x^j+q'(x)) $$ with $i+j=n$. But then $$x^iq'(x) + x^jq(x) + q(x)q'(x)=-x - 1.$$ forces $$ x^iq'(x) + x^jq(x) = -x $$ $$ q(x)q'(x) = -1. $$ Hence, $q(x), q'(x)$ are constant, which implies $i=j=1$ (so we already have $p(x)$ irreducible for $n>2$).

Now, since $q(x), q'(x)$ are constant, we refer to them as $q, q'$ respectively. Then $$ qx + q'x = -x $$ implies $q+q'=-1$. But then $$q+q'=-1$$ $$q^2+qq' = -q$$ $$q^2-1 = q$$ is a contradiction.

share|improve this answer
I don't think that the "forces" part is right. Why does that happen? Why cannot for example $qq'=x^2-1$ and $x^iq'(x) + x^jq(x) = -x-x^2$? Note that there can be a lot of terms in the above line which cancel eachother.... –  N. S. May 16 '13 at 16:20
That's a good point. I think it can be fixed with some argument on the degrees of $q$ and $q'$. –  William Stagner May 16 '13 at 16:29
Fixing it might not be that easy, since you have two parameters in that equation. –  N. S. May 16 '13 at 16:30
I would be completely shocked that an elementary argument would succeed. I don't believe there's any known proof of the irreducibility (for general $n$) other than the proof Selmer gave back in the 1950s. Selmer himself points out in his paper that no known irreducibility tests at that time seemed to work on the family of polynomials $x^n-x-1$ for general $n$, and that's why he was led to figure out his proof. –  KCd May 16 '13 at 18:35
I take back my comment that there's no other proof than Selmer's. See my answer. –  KCd May 18 '14 at 21:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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