# Irreducible Polynomial in Field of 2 Elements?

How do I show that $f(t) = t^2 + t +1$ is irreducible in $K[t]$, where $K = \{0,1\}$?

I know how to tackle this over $\mathbb{Z}$ or $\mathbb{Q}$ using Guass or Eisenstein say...but I'm a little unsure how to proceed in this case.

Any help is much appreciated.

-
All you have to show is that $f$ does not have a root in $\mathbf F_2$. Do you see why? – Dylan Moreland Apr 13 '12 at 12:33
Yes I see actually, but what if $f(t)$ doesn't have a linear factor but maybe a quadratic factor or a factor of higher order... If $deg f = 10$ say, and $f(0)\neq 0$ and $f(1)\neq 0$ - does this imply $f$ is irreducible? – rk101 Apr 13 '12 at 12:37
That's a different question, and the answer is certainly no: you could take the $f$ in your original question and square it, for example. – Dylan Moreland Apr 13 '12 at 12:56
There are general techniques to check irreducibility of polynomials over a finite field like $\mathbb{Z}/2\mathbb{Z}$, as mentioned in this previous Question. No, for such polynomials of degree 10, knowing $f(0)=1$ and $f(1)=1$ does not imply $f$ is irreducible. E.g. take the polynomial in your Question and raise it to the fifth power. – hardmath Apr 13 '12 at 13:03

Suppose $f(t)$ is reducible.(then we have to show that it is contradiction)

$f(t) = (t+a)(t+b)$ where a and b are in $K$

Case 1: $a =0,b=0$

$f(t)= t^2$. This is contradiction.

Similarly we can prove remaining cases.

Case 2: $a=1,b=1$

Case 3: $a=0,b=1$ or $a=1,b=0$

-
Yes I see actually, but what if f(t) doesn't have a linear factor but maybe a quadratic factor or a factor of higher order... If degf=10 say, and f(0)≠0 and f(1)≠0 - does this imply f is irreducible? – rk101 Apr 13 '12 at 12:44
It is depending on given function – Prasad G Apr 13 '12 at 12:48
Is there a general method in this case? – rk101 Apr 13 '12 at 12:49
Several methods. The most naive, but for low degrees quite applicable one is as follows: For degrees 2 and 3 you know all irreducible polynomials (check for roots). For degree 4, all you need to do is check for roots, then check whether the polynomial is divisible by the irreducible polynomials of degree 2. Rinse and repeat. For higher degrees (I'd say >6), see Rabin's algorithm. – m_l Apr 13 '12 at 13:11

As said by a couple of users, this polynomial does not have a root in $\mathbb{F}_{2}$ and since it is of degree $2$, it is irreducible.

You ask if $f$ can have a quadratic factor or a factor of higher degree, assume that such factor $g$ exist, i.e. $f=gh$ for some polynomial $h\neq0$.

Then $\deg(f)=\deg(g)+\deg(h)$ implies $\deg(g)\leq \deg(f)=2$ and by our assumption $\deg(g)\geq2$ so we can not have that $f$ have a factor of higher degree. So we have $f=gh$ and since $\deg(f)=\deg(g)=2$, it holds that $\deg(h)=0$, i.e. $h\in\mathbb{F}_{2}$ is a constant polynomial. Since $h\neq0$ (otherwise $f=gh=0$) we have $h=1$, hence $f=g$.

That is you can not decompose $f$ (not to a linear factor as you said, not to a quadratic factor or higher by this explanation)

-