# Irreducibility of $x^n-x-1$ over $\mathbb Q$

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$?

• How do you know that there is an $m$ such that $\phi(m) = n$? Commented May 16, 2013 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]$. Commented May 16, 2013 at 16:15
• @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
Commented May 16, 2013 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! Commented May 19, 2013 at 18:06
• @Corvus — To echo TedShifrin, the polynomial ring $\mathbb{F}_{p}[X]$ is infinite, the set $\mathrm{Map}(\mathbb{F}_{p}, \mathbb{F}_{p})$ is finite. Hence the natural map $\mathbb{F}_{p}[X] \to \mathrm{Map}(\mathbb{F}_{p}, \mathbb{F}_{p})$ is not injective. To stress the difference, let me ‘prove’ that $\mathbb{F}_{2}$ is algebraically closed: Take a non-constant polynomial $f$, then $f$ is not constant $1$, and as $\mathbb{F}_{2}$ has only two elements, $f(x) = 0$ for some $x \in \mathbb{F}_{2}$. Thus $f$ has a zero, hence $\mathbb{F}_{2}$ is algebraically closed. $\square$ Spot the error.
– jmc
Commented Jun 16, 2014 at 11:26

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

Update: for another application of this method to prove irreducibility of a family of polynomials, see the MO post here.

• This is outlandishly clever! Make sure it gets included into some textbook or lecture notes :-) Commented Jun 16, 2014 at 3:56
• Could the argument presented here be used to solve this problem as well ? Commented Feb 7, 2015 at 14:51
• @fedja the above proof and some extensions of it are now in "lecture notes". See kconrad.math.uconn.edu/blurbs/ringtheory/irredselmerpoly.pdf.
– KCd
Commented Feb 11, 2019 at 11:05
• @KCd Very sorry to bother you with this, but here the asker thinks that a variant of these polynomials (mentioned in your last paragraph) have the full Galois group as well (with supporting evidence by SAGE). Have you heard of that result? Or can you think of a way towards proving it? Commented Jun 17, 2019 at 14:10
• @JyrkiLahtonen I have put an answer at that link.
– KCd
Commented Jun 17, 2019 at 16:58

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.

• 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
Commented May 16, 2013 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
Commented Jun 20, 2013 at 0:32
• @KCd: That is interesting. Thanks!
– bzc
Commented Jun 20, 2013 at 14:23
• See my answer for a sketch of a proof that is easier to work through than Selmer's.
– KCd
Commented May 18, 2014 at 21:46
• @awllower: It's updated now.
– bzc
Commented Oct 30, 2014 at 0:43