# 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$? 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]$. 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
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! 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
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 :-) Jun 16, 2014 at 3:56
• Could the argument presented here be used to solve this problem as well ? 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
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? Jun 17, 2019 at 14:10
– KCd
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
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
Jun 20, 2013 at 0:32
• @KCd: That is interesting. Thanks! 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
May 18, 2014 at 21:46
• @awllower: It's updated now. Oct 30, 2014 at 0:43