# Irreducibility of some trinomials modulo $p$

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)

and

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

-
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 mathoverflow.net/questions/56579 (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

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

-
@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