1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ All you have to show is that $f$ does not have a root in $\mathbf F_2$. Do you see why? $\endgroup$
    – Dylan Moreland
    Apr 13, 2012 at 12:33
  • $\begingroup$ 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? $\endgroup$
    – rk101
    Apr 13, 2012 at 12:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dylan Moreland
    Apr 13, 2012 at 12:56
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Apr 13, 2012 at 13:03

2 Answers 2

Reset to default
1
$\begingroup$

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$

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – rk101
    Apr 13, 2012 at 12:44
  • $\begingroup$ It is depending on given function $\endgroup$
    – Prasad G
    Apr 13, 2012 at 12:48
  • $\begingroup$ Is there a general method in this case? $\endgroup$
    – rk101
    Apr 13, 2012 at 12:49
  • $\begingroup$ 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. $\endgroup$
    – m_l
    Apr 13, 2012 at 13:11
0
$\begingroup$

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)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .