Irreducibility of some trinomials modulo \$p\$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T19:44:06Z http://mathoverflow.net/feeds/question/56506 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56506/irreducibility-of-some-trinomials-modulo-p Irreducibility of some trinomials modulo \$p\$ Luis H Gallardo 2011-02-24T09:20:32Z 2011-05-24T22:59:07Z <p>Let \$n>1\$ be an integer. An old result of Selmer, See Theorem 1, page 289 in</p> <p><a href="http://www.mscand.dk/article.php?id=1472" rel="nofollow">http://www.mscand.dk/article.php?id=1472</a>, </p> <p>(If the link does not work try googling: <code>selmer trinomials</code>)</p> <p>says that</p> <p>\$\$ S(n) = x^n-x-1 \$\$ is irreducible over the the field \$k= \mathbb{Q}\$ of rational numbers.</p> <p>Question : What is known about the possible irreducibility (or not) of the sligthly more general trinomial</p> <p>\$\$ T(n,m) = x^n - x^m -1 \$\$</p> <p>(with \$0 &lt; m &lt; n\$)</p> <p>over the prime field</p> <p>\$\$ k =GF(p) \$\$</p> <p>such that (say)</p> <p>(a) \$p>2,\$</p> <p>(since seems there are many known results for binary polynomials)</p> <p>and</p> <p>(b) \$n\$ goes to infinity when \$p\$ goes to infinity.</p> <p>EDIT: Observe that something can be said about the parity of the number of irreducible factors: Use Stickelberger's parity theorem.</p> http://mathoverflow.net/questions/56506/irreducibility-of-some-trinomials-modulo-p/56605#56605 Answer by Aaron Meyerowitz for Irreducibility of some trinomials modulo \$p\$ Aaron Meyerowitz 2011-02-25T06:41:24Z 2011-02-25T11:53:43Z <p>Based on a small number of small cases I suspect that the majority of those of those do factor. </p> <p>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. </p> <p>For \$p=19, \$ \$x^k-x-1\$ factors for \$2 \le k \le 18\$ except for \$k=4\$ and \$k=15\$.</p>