2
$\begingroup$

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]$?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Alon Amit Aug 1 '18 at 6:58
  • $\begingroup$ 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. $\endgroup$ – Ecotistician Aug 1 '18 at 7:01
  • 1
    $\begingroup$ Perhaps your professor wants a combinatorial argument ? Like, count polynomials, count reducible ones and deduce that there must be irreducible ones. $\endgroup$ – Max Aug 1 '18 at 8:17
  • $\begingroup$ 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. $\endgroup$ – Ecotistician Aug 1 '18 at 9:04
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.