Consider $f(x) = x^5 + 2x^4 + x^3 + 2x^2 + x + 1 \in \mathbb{F}_3[x]$. Find the smallest $m\in\mathbb{N}$ such that f(x) divides $x^{3^m}-x$.

Question

Consider $f(x) = x^5 + 2x^4 + x^3 + 2x^2 + x + 1 \in \mathbb{F}_3[x]$. I see that $f(x) = (x^2+x -1)\cdot(x^3 + x^2 + x - 1)$, both of which are irreducible / prime polyonimals (Recall that since $\mathbb{F_{3}} $ is a field, $\mathbb{F}_{3}[x] $ is a UFD so primes = irreducibles). I wish to find the smallest $m \in \mathbb{N}$ such that f(x) divides $x^{3^m} - x$. Using properties of prime elements this is equivalent to finding smallest m such that $x^3 + x^2 + x - 1$ or $x^2+x -1$ divides $x^{3^m- 1} - 1$. I checked for m = 1, 2. I guess I can continue doing this this way, but I was wondering if there is a more efficient and elegent way to find this m. Any help/suggestions will be appreciated.

Answer 1

$a(x) = x^3+x^2+x-1$ divides $x^k-1$ (over $\mathbb F_3$) iff $k$ is divisible by $13$ (i.e. $13$ is the order of $x$ in the multiplicative group of $\mathbb F_3[x]/a(x)$), and $b(x) = x^2+x-1$ divides $x^k-1$ over $\mathbb F_3$ iff $k$ is divisible by $8$. So $a(x)\cdot b(x)$ divides $x^k-1$ over $\mathbb F_3$ iff $k$ is divisible by $\text{lcm}(8,13)=104$. Thus you want $104 \mid 3^m-1$, which is true iff $m$ is divisible by the multiplicative order of $3$ mod $104$, which is $6$.

Answer 2

Recall that there is a unique field of order $\mathbb{F}_{3^n}$ for each $n$, and that $\mathbb{F}_{3^n}\subseteq \mathbb{F}_{3^m}$ if and only if $n|m$.

You are of course looking for the splitting field of your original polynomial.

The splitting field of $x^2+x-1$ has degree $2$ over $\mathbb{F}_3$; so that polynomial splits over $\mathbb{F}_{3^2}$. If you add a root of $x^3+x^2+x-1$ you get an extension of degree $3$; so the smallest extension that has roots for both $x^2+x-1$ and $x^3+x^2+x-1$ has degree $6$ over $\mathbb{F}_3$ (since these two extensions have coprime degree, and so their compositum has degree equal to their product). The only question is whether $x^3+x^2+x-1$ splits over $\mathbb{F}_{3^6}$, or if it factors as a linear factor plus an irreducible quadratic. In the former case, the $m$ you are looking for is $6$; in the latter, it is $12$.