Galois field and polynomials?

Question

Show there are only two polynomials of degree 3 over $\mathbb{F}_2$ such that it is irreducible and all other degree 3 polynomials can be reduced. So $x^2 = x$ and $x = -x$

I cant think of anything of the form$ ax^3 + bx^2 + cx +d$ such that it cannot be reduced. For example, $x^3$ itself can be $x^3=(x^2)x = (x)x = x^2$ which is also equivalent to $x$ and $-x$?

Answer 1

Well, you obviously need to move past monomials. Remember that a polynomial of degree $2$ or $3$ can factor only if it has a root, so eliminate the polynomials that have $0$ as a root (constant term $0$) and the polynomials that have $1$ as a root (an even number of nonzero terms), and what are you left with?

$f(x) = x^3+x+1$ and $f(x) = x^3+x^2+1$

Answer 2

What are all polynomials of degree $3$ over $\mathbb{F}_2$??

How many are there??? $x^3+ax^2+bx+c$ where $a,b,c\in \{0,1\}$

For irreducibility, I can not consider $c=0$

(if $c=0$,then $0$ would be a root).

So, we have $x^3+ax^2+bx+1$ where $a,b\in \{0,1\}$

So, we have to check for only $4$ polynomials :

$x^3+1,x^3+x^2+1,x^3+x+1,x^3+x^2+x+1$.

It is easy to see that $x^3+x^2+x+1$ and $x^3+1$ are reducible with $1$ as root.

So, we left with only two polynomials $x^3+x^2+1,x^3+x+1$ which has no root..

Answer 3

While we have $x^2=x$ whenever we plug in any element of $\mathbb F_2$ for $x$ (so $x^2$ and $x$ are the same when viewed as functions $\mathbb F_2\to\mathbb F_2$), we do not have $x^2=x$ when talking about polynomials $\in\mathbb F_2[x]$. For example we have $\deg x^2=2$ and $\deg x=1$.

(On the other hand, your observation that $x=-x$ is correct).

The general polynomial of degree $3$ looks like $x^3+ax^2+bx+c$ with $a,b,c\in\mathbb F_2$. If $c=0$, we have $x$ as a factor, so we get to $x^3+ax²+bx+1$. Then if $a=b$ we see that $1$ is a root, and so we get to $x^3+ax^2+(1-a)x+1$, that is there are only two possibilities $$x^3+x^2+1\qquad\text{and}\qquad x^3+x+1. $$ Remains to show that these are irreducible. But as they are of degree, at least one proper factor would have to be of degree $1$. As we have specififcally excluded the possibility that $0$ or $1$ are a root, we are done.

Answer 4

We can prove this without calculating either of the polynomials. We make three observations:

• There are exactly 8 polynomials of degree 3.
• A polynomial of degree 3 is reducible if and only if it has a root.
• There is exactly one irreducible polynomial of degree 2.
• There are exactly two linear polynomials.

Therefore, the reducible polynomials of degree 3 must be either a product of three linear factors (4 possibilities), or a product of a linear polynomial with an irreducible quadratic (2 possibilities). So the number of irreducible polynomials of degree 3 is $8-(4+2) = 2$.