# Showing there are irreducible polynomials of abitrarily large degree over $\mathbb{Z}/2[x]$

To prove this, I know that you can assume there are only finitely many such irreducible polynomial, take their product + 1 which will result in this new polynomial not having any factor in the assumed finite set of irreducible polynomial, contradiction.

But my professor is asking us to use the number $2^n-1$ (the number of polynomials of degree less than n in $\mathbb{Z}/2[x]$) to prove it, I have no idea why, or how you would prove it using this specific number, seems unnecessary, but I would really like to know how you would use this number to produce an easier proof for $\mathbb{Z}/2[x]$?

• Perhaps you've learned a few other things, too? Properties of finite fields, or existence of algebraic closure, or the factorization of $x^{2^n}-x$, things like that? – Alon Amit Aug 1 '18 at 6:58
• I have, And I know that you can use those facts to prove that there are irreducible polynomials of ANY degree, but I am trying to prove this particular problem using the technique that this professor wants, using the number of polynomials of degree less than or equals to n. – Ecotistician Aug 1 '18 at 7:01
• Perhaps your professor wants a combinatorial argument ? Like, count polynomials, count reducible ones and deduce that there must be irreducible ones. – Max Aug 1 '18 at 8:17
• Counting the reducible ones seems pretty tedious, and I'm not seeing how it is neccesarily less than 2^(N+1)-1 for N the degree of the highest degree irreducible polynomial. – Ecotistician Aug 1 '18 at 9:04

Consider the polynomial $$g(x) := x^{2^n - 1} - 1.$$ We may form the splitting field $\mathbb F$ of $g$ over $\mathbb Z/2$. Then we claim that $\mathbb F$ has degree $n$. Indeed, $g'(x) \neq 0$ for $x \neq 0$ (formal differential), so $g$ does not have double roots (by the product rule). Hence, $\deg \mathbb F \ge n$, and this is in fact all we need. (Moreover, the roots of $g$ united with zero form a field inside $\mathbb F$, which is hence equal to $\mathbb F$ by the definition of a splitting field, so $\deg \mathbb F = n$.)
Then find a primitive element of the multiplicative group. Its irreducible polynomial will have order $n$.