# two results about irreducible polynomials over $F_2$

Theorem 1 For any given $n(n\geqslant2)$ , there exist a $m$, such that $x^n+x^m+1$ is irreducible over binary field.

Theorem 2 For any given $n(n\geqslant4)$ , there exist a $n_1,n_2,n_3$, such that $x^n+x^{n_1}+x^{n_2}+x^{n_3}+1$ is irreducible over binary field.

To some $n$(sucn as $n=8$) Theorem 1 doesn't hold any more, but to Theorem 2 it seems that it holds always if $n\geqslant4$. Now i want to prove this theoretically, i have considered it for a very long time. Who can help me! please....

-
Just one remark. A random polynomial of degree $n$ over the field of two elements is irreducible with probability $1/n$ (subtract a correction term negligible for larger $n$). That suggests that Theorem 1 is touch and go, and that Theorem 2 is likely to be true (or at least have only very few exceptions). This is somewhat in line with what Gerry Myerson found. I also think that these questions are difficult. –  Jyrki Lahtonen Aug 11 '13 at 19:28

## 1 Answer

There is a lot of work on irreducible trinomials. This paper says, among other things, that irreducible trinomials over the field of two elements don't exist if $n$ is a multiple of $8$. This paper mostly works over the field of three elements, but it gives references to papers that deal with the two-element field. Another paper with some relevant results and references is this one.

-
Basically, type "irreducible trinomial" into the web and get many papers. –  Gerry Myerson Aug 11 '13 at 1:41
it seems that what you say is not helpful to prove $Theorem 2$ –  Alex Aug 11 '13 at 1:57
What I say is not helpful, but where I point, is. If you look at those papers and the other ones that come up in a search for irreducible trinomial, you will find that some of them go on to look for "pentanomials". I got the impression that it's an unsolved problem, but I didn't read anything too closely --- that's your job! –  Gerry Myerson Aug 11 '13 at 2:02