# Factoring in Z3[x]

I need to factor $x^6+x^4+x^2+1$ into irreducible parts in $Z_3[x]$. Obviously this polynomial reduces to $(x^4+1)(x^2+1)$ which is irreducible in $Z[x]$, but I'm not sure how to confirm that it's irreducible in $Z_3[x]$. I've tried trial and error, and haven't found anything but would love some suggestions if anyone has ideas.

Just a heads up, I'm working ahead of my class since I have to work later this week and won't have time to wait for the lecture notes before finishing the assignment. Apologies if I've missed something obvious.

-
The quick way to see that $x^4+1$ factors $\pmod 3$ is to note that $x^4+1|x^9-x$, and $x^{3^k}-x$ is the product of all monomial primes of degree $d|k$. But you can also factor $x^4+1$ by hand, if you like. – Thomas Andrews Nov 20 '12 at 21:24
The factorization $x^4 + 4 = (x^2 + 2x + 2)(x^2 - 2x +2)$ is popular. – Shubhodip Mondal Nov 20 '12 at 21:35
One way to see that those three quadratics are irreducible is because they have no roots, thus cannot split (which is the only way they can factor, i.e. if they split in linear factors). Combining our comments, you're pretty much done. – Patrick Da Silva Nov 20 '12 at 21:36
There are only 3 monic linear polynomials and 9 monic quadratic polynomials. You could test $x^4+1$ for divisibility by all of them directly. Or, you could construct $\mathbb{F}_9$, and then test if $x^4+1$ has any roots in $\mathbb{F}_3$ or $\mathbb{F}_9$. (in both cases, checking for a degree 3 factor is redundant, since you can obtain the same information by checking for a linear factor) – Hurkyl Nov 20 '12 at 22:21

The roots of any polynomial over $\mathbb{F}_3$ lie in some finite extension field $\mathbb{F}_{3^n}$.

The roots of $x^4 + 1$ are all primitive eighth roots of unity. Therefore, we know they live in any extension field such that $8 \mid 3^n - 1$.

The smallest such field is the one with $n=2$. However, this is merely a degree 2 extension! The minimal polynomial of an eighth root of unity in characteristic 3, then, is a quadratic polynomial. The irreducible factorization of $x^4 + 1$ over $\mathbb{F}_2$, therefore, must be a product of two quadratic polynomials.

We can say more: if $\zeta$ is a primitive eighth root of unity, then $\zeta$ and $\zeta^3$ are roots of one factor, and $\zeta^5$ and $\zeta^{15} = \zeta^7$ are roots of the other factor. We have a factorization

$$x^4 + 1 = (x^2 - (\zeta+\zeta^3) x + \zeta^4) (x^2 - (\zeta^5 + \zeta^7) x + \zeta^4)$$

If you construct a realization of the field $\mathbb{F}_9$, you could do the arithmetic to simplify the coefficients to elements of $\mathbb{F}_3$.

But we can cheat: from ordinary arithmetic in characteristic 0, we know the standard eighth roots of unity

• $\zeta = \frac{\sqrt{2}}{2} (1 + \mathbf{i})$
• $\zeta^3= \frac{\sqrt{2}}{2} (-1 + \mathbf{i})$
• $\zeta^5 = \frac{\sqrt{2}}{2} (-1 - \mathbf{i})$
• $\zeta^7 = \frac{\sqrt{2}}{2} (1 - \mathbf{i})$

and so the factorization should simplify to

$$x^4 + 1 = (x^2 - \frac{\mathbf{i}\sqrt{2}}{2} x + (-1))(x^2 - \frac{-\mathbf{i}\sqrt{2}}{2} + (-1))$$

In characteristic 3, $(\mathbf{i} \sqrt{2})^2 = -2 = 1$, so if we pick $1$ as the product of square roots, we should have

$$x^4 + 1 = (x^2 - \frac{1}{2} x + (-1))(x^2 - \frac{-1}{2} + (-1)) = (x^2 - 2x - 1)(x^2 + 2x - 1)$$

and if we didn't believe that this "cheat" was actually a valid derivation, we can verify this factorization is correct directly.

-

Hint $\rm\ mod\ 3\!:\,\ x^4\!+1\, \equiv\, x^4\!-3x^2\! + 1\,\equiv\, (x^2\!-1)^2 - x^2 =\,$ difference of squares

$\rm\ mod\,\ 2n\!+\!1\!:\,\ x^4\!+n^2\equiv\,x^4\!-(2n\!+\!1)\,x^2\! + n^2\equiv\, (x^2\!-\!n)^2\! - x^2$

-