2

Problem statement:

Show that $x^3+x+1$ is irreducible over $\mathbb{F}_2$ and let $\theta$ be a root. Compute the powers of $\theta$ in $\mathbb{F}_2$.

I am having trouble computing the powers of $\theta$. $x^3+x+1$ is irreducible, since any cubic polynomial over a field is reducible if and only if it has a root in the field. Since $\mathbb{F}_2=\{0,1\}$, we see that none of these is a root of $x^3+x+1$.

To compute the powers of $\theta$, note that $\theta^3+\theta+1=0$. Hence $\theta^3=-(\theta+1)$. Is this a good enough answer for $\theta^3$?

To compute $\theta^2$, note that $\theta = -(\theta^3+1)$. Therefore, $$\theta^2=(\theta^3+1)^2 = \theta^6 + 2\theta^3 + 1 = (-\theta-1)^2-2\theta-2+1,$$ which just reduces to $\theta^2$. Any ideas for computing these powers?

Thanks!

Numbersandsoon
  • 2,910

3 Answers3

4

You are right, $\theta$ is not in $\mathbb{F}_2$, since $x^3+x+1$ is irreducible over this field. But we have a recursion, i.e., $\theta^3=\theta+1$. Then just multiply with $\theta$ repeatedly: $$ \theta ^4=\theta ^2+\theta,\; \theta^5=\theta^2+\theta+1,\; \theta^6=\theta^2+1, \; \theta^7=1. $$

Dietrich Burde
  • 130,978
  • 1
    So if the problem statement really asks to compute the powers of $\theta$ in $\mathbb F_2$ (and not in $\mathbb F_2[\theta]$), i.e. to determine all $k\in\mathbb N$ such that $\theta^k\in \mathbb F_2$, this list shows that the first such $k$ is $k=7$ – Hagen von Eitzen Apr 25 '14 at 13:11
  • Great! I understand. Yes, the problem statement does say in $\mathbb{F}_2$, perhaps they meant $\mathbb{F}_2[\theta]$, I guess that would make more sense. Only $\theta^7 \in \mathbb{F}_2$ for $k \leq 7$, and then it repeats. I get it. Thanks! – Numbersandsoon Apr 25 '14 at 13:52
1

Note that if $f(x)=x^3+x+1$ any polynomial $g(x)$ can be written as $g(x)=f(x)q(x)+r(x)$ with the degree of $r(x)$ less than $3$.

Then $g(\theta)=r(\theta)$.

If $r_1(x)$ and $r_2(x)$ are two polynomials of degree $2$ or less, and $r_1(\theta)=r_2(\theta)$ then $\theta$ is a root of the polynomial $r_1-r_2$, which has lower degree than $f$. If we didn't have $r_1=r_2$, we could find a common factor for $(f, r_1-r_2)$ and $f$ would not be irreducible.

Setting $r_1(x)=x^2$ we see that we can't get a lower degree expression for $\theta^2$. The best you can do for any polynomial in $\theta$ is to reduce it to an expression which is at most quadratic. There are eight such expressions.

Mark Bennet
  • 100,194
0

$\;\theta\;,\;\;\theta^2\;$ are different elements which can't be expressed as a linear expression of each other (this is just as saying they're linearly independent elements of $\;\Bbb F_2[\theta]\;$ over $\;\Bbb F_2\;$), but then

$$\theta^3+\theta+1=0\implies \theta^3=-\theta-1=\theta+1\pmod 2$$

$$\theta^4=\theta(\theta^3)=\theta(\theta+1)=\theta^2+\theta$$

and etc.

DonAntonio
  • 211,718
  • 17
  • 136
  • 287