The degrees of irreducible divisors of polynomials

Question

Indicate the degrees of irreducible divisors of polynomials

1. $x^5-2$ in $F_{67}[x]$;
2. $x^{28}-1$ in $F_{3}[x]$.

For first I found by Wolfram $x^5-2 = (x-41)(x^4+41x^3+6x^2+45x+36)$

How can I do it without Wolfram? And after I was trying to prove that second polynomial is irreducible (isn't it?) (that's way the answer would be $1, 4$ - looks nice) - but didn't succeed.

Answer 1

You could begin by finding the order of $2$ in $\Bbb{F}_{67}^*$. The order is a factor of $66$. The law of quadratic reciprocity tells us that $2$ is not a QR modulo $67$ as $67\equiv3\pmod8$. Therefore the order is even, i.e. either $2, 6, 22$ or $66$. The first two are immediately eliminated. Calculating $2^{22}$ takes a bit longer, but it turns out to be $\equiv37\pmod{67}$. Therefore the order is $66$, i.e. $2$ is primitive.

This implies that the zeros of $x^5-2$ have multiplicative orders either $66$ or $5\cdot66=330$. Exactly one of those zeros has order $66$, because raising to fifth power is a bijection in a cyclic group of order $66$, here $\Bbb{F}_{67}^*$. Therefore the other four roots all have order $330$.

The multiplicative group of the quadratic extension field $\Bbb{F}_{67^2}$ has order $67^2-1=66\cdot 68$. This is manifestly not divisible by five, so that field does not contain roots of unity of order $330$. This is equivalent to stating that $x^5-2$ has no quadratic factors over $\Bbb{F}_{67}$. We already saw that it has only a single linear factor, so it factors as a product of a linear and a quartic factor.

---

The other polynomial is similar. The roots of unity of orders $1,2,4,7,14$ and $28$ are its zeros. Those reside in extension fields of degrees $1,1,2,6,6$ and $6$ respectively. Remember that there are exactly $\phi(n)$ primitive roots of unity of order $n$, and if their minimal polynomial has degree $k$, this gives $\phi(n)/k$ irreducible factors. Leaving it to you to fill in the details.

Answer 2

In $F_{67}$, note that $x^{66}=1$ by Fermat's Little theorem. But $5$ and $66$ are coprime, so notice $x=x^{66}x^{-65}=(x^5)^{-13}=2^{-13}$. This can be computed easily by hand: we have $2^6 = 64\equiv-3$ so $2^{12}=9$ giving $2^{13} \equiv 18$. So $18x \equiv 1 \bmod{67}$. Finally, use the extended Euclidean algorithm to get $x = 41$.

Then polynomial division gives the second polynomial. Interestingly, the above method shows that the only root of $x^5-2$ in $F_{67}[x]$ is $41$, so if the second polynomial reduces, it does so as two irreducible quadratics.