Factoring a polynomial over $\mathbb{F}_{101}$.

Question

I am trying to show that the polynomial $f = X^5 + 69$ factors in linear factors over $\mathbf{F}_{101}$. I have found one root, namely $2$, since $2^5 = 32$, and so $2^5 + 69 = 101 = 0$. But I cannot find any other obvious roots, is there a way to obtain these? Or alternatively, is there a way to show this without getting the explicit factorization?

Maybe the observation that $f = X^5 - 2^5$ is helpful?

Answer 1

Hint: The field $\mathbf{F}_{101}$ contains fifth roots of unity because its multiplicative group is cyclic of order $100$. If $\alpha$ is one zero of your polynomial, and $\zeta$ is a fifth root of unity, then $(\zeta\alpha)^5=$____?

If you need to actually find those zeros, then you can find the fifth roots of unity by random poking as follows.

1. Pick a random integer $a\neq\pm1,0$. Calculate $x=a^{20}$ modulo $101$.
2. If $x\neq1$ then $x$ is a fifth root of unity for $x^5=a^{100}=1$. If so, proceed to step 3, otherwise go back to step 1, and try a different $a$.
3. If $x$ is one fifth root of unity, $x^2,x^3,x^4$ are the others.