3

Here's my homework problem:

Let $K = \mathbb{Z}_2[x] / \langle x^4 + x^3 + 1\rangle$. Show the polynomial $p(x) = x^3 + x + 1$ is irreducible in $K[x]$.

Since the polynomial is third-degree, I suppose it would be sufficient to show that it has no zeroes. But that would require a brute-force check of every element of $K$, of which there are many. Surely this isn't the only way?

So, my question is: what is the most practical proof technique for showing that this polynomial is irreducible?

Please don't solve the problem for me - I'm just looking for a nudge. Thanks!

Zev Chonoles
  • 129,973
GMB
  • 4,186
  • 2
    Something's weird here: you're using $x$ both in the definition of $K$ and in the polynomial $p$. Do you mean something more like: Let $K=\mathbb{Z}_2[t]/\langle t^4+t^3+1\rangle$, and show the polynomial $p=x^4+x^3+1$ is irreducible in $K[x]$? – Zev Chonoles Mar 06 '13 at 03:52
  • 1
    If $\alpha \in K$ is a root of $x^3+x+1$, then so are the conjugates $\alpha^2, \alpha^4, \alpha^8$ of $\alpha$ roots of $x^3+x+1$. Neither $1$ nor $0$ is a root of $x^3+x+1$ etc – Dilip Sarwate Mar 06 '13 at 03:54
  • 1
    By the way, LaTeX tip: < and > denote "less than" and "greater than", and using them for purposes other than this will produce strange spacing. The symbols you should be using, angle brackets, are obtained with the commands \langle and \rangle. – Zev Chonoles Mar 06 '13 at 03:55

2 Answers2

2

$$K\cong \Bbb F_{2^4}=\Bbb F_{16}\;\;,\;\;\Bbb F_2[x]/\langle x^3+x+1\rangle\cong\Bbb F_8$$

If $\,x^3+x+1\,$ were reducible in $\,K\,$ then $\,\Bbb F_{16}\,\,,\,\,\Bbb F_{8}\,$ would both contain a root of an irreducible polynomial of degree greater than one over the prime field $\,\Bbb F_2\,$...but this is impossible (why?)

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
1

A general remark: over finite fields there is a polynomial irreducibility test that is an an efficient analog of the impractical Pocklington-Lehmer integer primality test (e.g. see Section 3.4.3 of Cohen's text A Course in Computational Algebraic Number Theory). Below is a description of one form of this algorithm, from this Wikipedia page.

enter image description here

Math Gems
  • 19,574