Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $n>1$ be an integer. An old result of Selmer, See Theorem 1, page 289 in,

(If the link does not work try googling: selmer trinomials)

says that

$$ S(n) = x^n-x-1 $$ is irreducible over the the field $k= \mathbb{Q}$ of rational numbers.

Question : What is known about the possible irreducibility (or not) of the sligthly more general trinomial

$$ T(n,m) = x^n - x^m -1 $$

(with $0 < m < n$)

over the prime field

$$ k =GF(p) $$

such that (say)

(a) $p>2,$

(since seems there are many known results for binary polynomials)


(b) $n$ goes to infinity when $p$ goes to infinity.

EDIT: Observe that something can be said about the parity of the number of irreducible factors: Use Stickelberger's parity theorem.

share|cite|improve this question
A previous answer about some (reducible) trinomial multiples of $x^2-x+1$ was deleted, taking some of my comments with it. I note that adding appropriate multiples of $x^3+1$ to $x^2-x+1$, and then dividing by $(+-1)x^k$ as desired, generates a two parameter family of trinomials (with an exponent in each residue class mod 3) whose signs depend on the added multiples, and are all multiples of $x^2-x+1$. Related to this is (thanks to Mark Sapir and Gerry Myerson). Gerhard "Where Do Deleted Comments Go?" Paseman, 2011.02.24 –  Gerhard Paseman Feb 25 '11 at 7:22
Consider the $(2k+1)^n$ monic degree $n$ polynomials with all coefficients no larger in absolute value than $k$. One can see why "most" would be irreducible in $\mathbb{Z}[x]$ whereas many fewer would be irreducible in $\mathbb{Z}_p[x]$. Still, that seems like a pretty weak explanation of the fact that $x^n-x-1$ is always irreducible in $\mathbb{Z}[x]$ but appears to rarely be irreducible in $\mathbb{Z}_p[x]$. –  Aaron Meyerowitz Mar 3 '11 at 22:07
Something is known (See Theorem 3.86, page 131 of Lidl and Niederreiter's book Finite Fields, vol 20 of Encyclopedia of Mathematics and its Applications, reprinted 1987) about the number $N(q,n)$ of $a \in GF(q)$ that make the trinomial $$ S_n(x) =x^n+x+a $$ irreducible over $GF(q)$: $$ \vert N(q,n)- \frac{q}{n} \vert \leq B_n q^{1/2} $$ for some constant $B_n$ depending only on $n.$ –  Luis H Gallardo Mar 8 '11 at 23:46
Above: $n \geq 2$ and $p$ does NOT divide $2n(n-1).$ –  Luis H Gallardo Mar 8 '11 at 23:51

1 Answer 1

up vote 4 down vote accepted

Based on a small number of small cases I suspect that the majority of those do factor.

Let $r$ be a primitive root $\mod p$ then there is an $n$ such that $r^n=r+1 \mod p$. Then $x-r$ is a factor of $x^n-x-1$ in $\mathbb{Z}_p$. On average $n$ should be about $p/2$. Of course one can use $x^{n+p-1}-x-1$ but that seems like cheating. That is just cases with a linear factor.

For $p=19, $ $x^k-x-1$ factors for $2 \le k \le 18$ except for $k=4$ and $k=15$.

share|cite|improve this answer
@Aaron: Interesting idea. Can we say something when (say) $n \equiv 1 \pmod{p(p-1)}$ ? –  Luis H Gallardo Feb 25 '11 at 19:56
Most of the time they factor but not always.... –  Aaron Meyerowitz Feb 26 '11 at 0:53
For all prime numbers less than $103$ (not tried more since this begin to take some time in maple) the only irreducible polynomial $$ x^{p(p-1)+1}-x-1 $$ in $GF(p)[x]$ occurs when $p=5.$ –  Luis H Gallardo Mar 2 '11 at 23:00
My comment was that $x^{jp(p-1)+1}-x-1 $ factors "most of the time but not always" $\mod p$. That is just based on small $p$ and $j$, but it does seem pretty dramatic.Up to $j=29$, $x^{20j+1}-x-1$ factors $\mod 5$ except for $j=1,17$ and $x^{6j+1}-x-1$ factors $\mod 3$ except for $j=2,12,20.$ –  Aaron Meyerowitz Mar 3 '11 at 22:20
It appears that for prime $p=4k-1$ one has that $x^2+x+2k$ is a factor of $x^{p^2-p+1}-x-1$. I have no proof though. –  Aaron Meyerowitz Mar 4 '11 at 2:38

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.