# Is $t^4+7$ reducible over $\mathbb{Z}_{17}$?

Is $f=t^4+7$ reducible over $\mathbb{Z}_{17}$?

Attempt: I checked that $f$ has not roots in $\mathbb{Z}_{17}$, so the only possible factorization is with quadratic factors.

Assuming $f=(t^2+at+b)(t^2+ct+d)$, we have $bd=7$, $a+c=0$ and $ac+b+d=0.$ But it is cumbersome to find if there are solutions for these equations.

I know certain tools to prove the irreducibility of a polynomial over rings like $\mathbb{Z}$ or $\mathbb{Q}$ such as Gauss and Eisenstein's criteria. But over finite rings like $\mathbb{Z}_n$, I don't know how to prove the irreducibility of a polynomial with degree higher than $3$. Finding roots allows me to find linear factors, but I cannot use this technique to find quadratic factors. What kind of tool may I use in this case?

• In this case, brute force by computer would suffice, though of course something that can be reasoned out or computed by hand is preferable. Jul 17 '13 at 4:10
• There is one further condition: $a d+b c=0$. Adding this condition shows that there are no solutions and the polynomial is irreducible, which is confirmed by WA.
– lhf
Jul 17 '13 at 4:43
• Macaulay2 tells me this is irreducible. Code: R=ZZ/17[x]; f=x^4+7; isPrime(f) The output is: true. Alternatively, factor f gives back $x^4+7$. Jul 17 '13 at 4:47

It seems that we need only elementary tools to show the irreducibility in the comments. But let me introduce one interesting approach, called the Berlekamp algorithm, that one can calculate by hands, in a systematic way.
Firstly, let $\beta=\{1,x,\cdots,x^3\}$ be a basis for $F_{17}/(x^4+7)F_{17}$. Then we consider the automorphism $\sigma_{17}=\sigma$ which takes $f$ to $f^{17}$, with respect to the basis $\beta$.
$$\sigma: \begin{pmatrix}1&0&0&0\\0&4&0&0\\0&0&-1&0\\0&0&0&-4\end{pmatrix}.$$
Now denote the matrix of $\sigma-\iota$ by $B$, which is $$=\begin{pmatrix}0&0&0&0\\0&3&0&0\\0&0&-2&0\\0&0&0&-5\end{pmatrix}.$$
Since this matrix has kernel of dimension $1$, we conclude that $f$ is irreducible!
Why? It depends upon the following lemma:

Lemma
If $h\in F_q[x]$ is monic and such that $h^q\equiv h\pmod f$, then $f=\prod_{c\in F_q}\gcd(f(x),h(x)-c)$.

Since the proof is easy, we omit it here.
Furthermore, by definition, we know that $h$ must belong to the kernel of $\sigma_q-\iota$. Apparently, $h=1$ is always such one polynomial, and hence $\rho:=\sigma-\iota$ always has a kernel of dimenson $\ge1$; this is called the trivial factorisation.
Now let $f$ have $k$ irreducible factors $f_i$. If $h$ satisfies the conditions in the lemma, then each $f_i$ divides one of $h(x)-c$, so that $h\equiv c\pmod {f_i}$. As a consequence, we find that the dimension of the space of such $h$ is exactly $k$. Since this space is just the kernel of $\sigma_q-\iota$, we now see how one can conclude that our $f$ is irreducible as above.
In general, if there are non-trivial solutions to $h^q\equiv h\pmod f$, then we shall write out the factorisation $f(x)=\prod_{c\in F_q}\gcd(f(x),h(x)-c)$, and examine each factor therein respectively.

Summary
The key idea here is the matrix denoted by $B$ above. Its nullity (dimension of its kernel) is exactly the number of irreducible factors of $f$. If this number is just $1$, then $f$ is irreducible. If there are non-trivial polynomials in that kernel, write out the corresponding factorisation to reduce further things.
Note, however, that the nullity of $B$ might be $\not=0$, while $f$ is still irreducible. In that case, the only way is to examine each greatest commen divisor $\gcd(f(x),h(x)-c)$.

If any inappropriate points occur, tell me, so that I can appropriate it. Thanks in advance.

• @JyrkiLahtonen Glad that someone likes it. :) Jul 17 '13 at 6:28
• I see, if a non-trivial solution $h$ exists, we can get a non-trivial factor of $f$. But I don't understand why such $h$ need to exist. How do we get $k$ linear independent solutions from $k$ irreducible factors of $f$?
– Dune
Jul 17 '13 at 10:55
• @Dune It is because the dimension of the space is eaxctly $k$. For more details, you can consult the book finite fields. It is explained in chapter four. Hope you have a great time reading that book! :) Jul 18 '13 at 1:39
• @awllower Thank you for this link! I got it now - the Chinese Remainder Theorem provides the existence of non-trivial $h$. Just define $h :\equiv c_i \mod f_i$ (provided that $f$ is square-free). The book looks interesting. I will surely read it when I find time. :)
– Dune
Jul 18 '13 at 12:31
• @Dune Glad that you enjoy this theory! :D Jul 19 '13 at 3:15

Let $\alpha$ be a root of $f$ in some extension field of $\mathbb{Z}_{17}$. We know that $\alpha^4=-7=10$. Either brute force checking (won't take long!) or toying with quadratic reciprocity and such shows that $10$ is not a quadratic residue modulo $17$. As $\mathbb{Z}_{17}^*$ is cyclic of order $16$, this means that the order of $10$ is exactly $16$ (if it were a proper factor, $10$ would have to be a square).
This allows us to deduce that $\alpha$ is primitive root of unity of order $64$. Therefore $\alpha$ cannot be a zero of a quadratic polynomial over $\mathbb{Z}_{17}$, because the zeros of such polynomials belong to the field $\mathbb{F}_{289}$ of $17^2=289$ elements. The contradiction comes from the fact that the multiplicative group of $\mathbb{F}_{289}$ is cyclic of order $288$ but $288=2^5\cdot3^2$ is not divisible by $64=2^6$.
The relations between the coefficients $a,b,c,d$ are:
$$bd=7, ad+bc=0, ac+b+d=0, a+c=0\,.$$
Therefore $0=ad+bc=a(d-b)$. Since $\mathbb Z_{17}$ is a field, then either $a=0$ or $b=d$. If $a=0$, then $c=0$, so $b+d=0$, which in turn implies $b^2=-7=10$, which is impossible (check for $k=-8,\dots,7$ that $k^2\equiv 10(\bmod\ 17)$ is not true). Thus $b=d$, and so $b^2=7$, which is also impossible in $\mathbb Z_{17}$. This contradiction shows the desired result.
• We can show the impossibility of $x^2=10$ by noting that $(\dfrac{10}{17})=(\dfrac{2}{17})(\dfrac{5}{17})=-1$ by quadratic reciprocity, where $(\dfrac{p}{q})$ is the Legendre symbol. Jul 17 '13 at 6:24