Find all irreducible polynomials of degrees 1,2 and 4 over $\mathbb{F_2}$.
Attempt: Suppose $f(x) = x^4 + a_3x^3 + a_2x^2 + a_1x + a_0 \in \mathbb{F_2}[x]$. Then since $\mathbb{F_2} =${$0,1$}, then we have either $0$ or $1$ for each $a_i$. Then we have two choices for the $4$ coefficients, hence there are 16 polynomials of degree $4$ in $\mathbb{F_2}[x]$.
Recall $f(x)$ is irreducible if and only if it has not roots. Then
$f_1 = x$ is irreducible because it has not roots
$f_2 = x + 1$ is also another irreducible polynomial.
$f_3 = x^4 + x^2 + x = x ( x^3 + x + 1) $ is reducible.
$f_4 = x^4 = x^3* x$ is reducible
$f_5 = x^4 + x + 1$
Can someone please help me? Is there a way I can save time in finding the irreducible polynomials, other than just trying to come up with polynomials. Any better approach or hint would really help! Thank you !
Best Answer
Degree $1$, clearly $x$ and $x+1$.
Degree $2$, notice the last coefficient must be one, so there are only two options, $x^2+x+1$ and $x^2+1$. Clearly only $x^2+x+1$ is irreducible.
Degree $4$. There are $8$ polynomials to consider, again, because the last coefficient is $1$, now notice a polynomial is divisible by $x+1$ if and only if the sum of its coefficients is even. So the only polynomials without factors of degree $1$ are four:
$x^4+x^3+x^2+x+1$
$x^4+x^3+1$
$x^4+x^2+1$
$x^4+x+1$.
Of course, we are missing the possibility it is the product of two irreducibles of degree $2$, but the only combination is $(x^2+x+1)(x^2+x+1)=x^4+x^2+1$.
Hence the irreducible ones are:
$x^4+x^3+x^2+x+1,x^4+x^3+1,x^4+x+1$