How to find the root of $x^4+1$ mod 3?

Question

$x^4+1$ is irreducible over $\mathbb{Q}$, but with some coefficient modulus, this is not the case. My question is how to find the root of $x^4+1$ mod 3? I think the root is not the integer, but how can we find it?

Answer 1

Observe that $x^4+1=x^4+4$ over $\mathbb{F}_3$. You should know how to factor $x^4+4$.

Note that $x^4+4=\left(x^2+2\right)^2-\left(2x\right)^2$.

---

Note that $x^4+1$ is reducible over $\mathbb{F}_p$ for every prime natural number $p$. The case $p=2$ is easy: $$x^4+1=(x+1)^4\,.$$ If $p\equiv1\pmod{4}$, then $\left(\frac{-1}{p}\right)=1$, so $$x^4+1=\left(x^2-a\right)\left(x^2+a\right)\,,$$ where $a$ satisfies $a^2=-1$. If $p\equiv 3\pmod{8}$, then $\left(\frac{-2}{p}\right)=1$, whence $$x^4+1=\left(x^2-bx-1\right)\left(x^2+bx-1\right)\,,$$ where $b^2=-2$. If $p\equiv7\pmod{8}$, then $\left(\frac{2}{p}\right)=1$, so that $$x^4+1=\left(x^2-cx+1\right)\left(x^2+cx+1\right)\,,$$ where $c^2=2$.

Answer 2

Here is a (naive?) way to approach such a problem:

$$x^4 + 1 = (x^2 + ax + 1)(x^2 + bx + 1) = x^4 + (a+b)x^3 + (ab+2)x^2 + (a+b)x + 1$$

From the original polynomial in which only the leading term and constant are nonzero, we end up with two equations in two variables to solve over $\mathbb{F}_{3}$:

$a + b = 0$ and $ab + 2 = 0$. The former says that $a = -b$, which makes the latter $b^2 = 2$; impossible in $\mathbb{F}_3$ as no number can be squared to yield remainder $2$ after division by $3$.

Let us try again our first approach of rewriting as quadratic factors, but this time we will use constant terms of $-1$ in each of the two factors:

$$x^4 + 1 = (x^2 + ax - 1)(x^2 + bx - 1) = x^4 + (a+b)x^3 + (ab-2)x^2 - (a+b)x + 1$$

We are again led to two equations in two variables, $a+b=0$ and $ab-2=0$. The same reasoning yields $a=-b$, but now the second equation becomes $b^2 = -2 \equiv 1$. The square roots of $1$ in $\mathbb{F}_3$ are $1$ and $2$. Let us try these factorizations, first with $b = 1$, which means $a = -b = -1 = 2$:

$$x^4 + 1 = (x^2 + 2x - 1)(x^2 + x - 1) \equiv (x^2 + 2x + 2)(x^2 + x + 2)$$

where the latter equivalence arises since $-1 \equiv 2$.

Next, consider $b = 2$, which means $a = -b = -2 = 1$:

$$x^4 +1 = (x^2 + x - 1)(x^2 + 2x - 1) \equiv (x^2 + x + 2)(x^2 + 2x + 2)$$

where the latter equivalence is again due to $-1 \equiv 2$.

As may have been expected, our two factorizations are the same, and we have successfully rewritten the quartic as a product of two quadratic polynomials with coefficients in $\mathbb{F}_3$. Moreover, these quadratic factors are irreducible, as can be seen (for example) by noting that they cannot factor into linear terms since there are no roots in $\mathbb{F}_3$ for either.