Find roots of polynomial in a finite field

Question

I need to build a field $L$ of 121 elements and find how many roots polynomial $g=x^9-1$ has in $L$. Then to find all these roots.

So, $121=11^2$ this is power of prime. We can build finite field of 121 elements by finding normal irreducible polynomial of of power 2. We can see that $x^9-1 = (x-1)(x^2+x+1)(x^6+x^3+1)$, lets take $h=x^2+x+1$ as irreducible since it does not have natural roots in $Z_{11}$. We can build the field $L=\{k\alpha+b + h(\alpha), k,b \in Z_{11}\}$ Instantly we can see that 1 is the root of $g$ because of $(x-1)$.

Am I right so far? How can I find other roots of $g$ or at least find their conunt?

Answer 1

Once you have constructed $L$, note that the multiplicative group $L^\times$ has order $120$ and so the solutions of $x^9=1$ are the same as the solutions of $x^3=1$ because $\gcd(120,9)=3$. There are exactly $3$ roots because $L^\times$ is cyclic. These roots are $1, u^{40}, u^{80}$, where $u$ is a generator of $L^\times$.

Answer 2

To construct a field with $121$ elements we just need an irreducible quadratic polynomial over $\mathbb{F}_{11}$.
For instance, since $\left(\frac{2}{11}\right)=-1$ ($2$ is not a quadratic residue $\!\!\pmod{11}$, since $11\equiv 3\pmod{8}$)
we have: $$ \mathbb{F}_{121}\simeq \mathbb{F}_{11}[z]/(z^2-2) \tag{1}$$ In general, the roots of $x^9-1$ are the ninth roots of unity, i.e. $1$, the primitive third roots of unity and the primitive ninth roots of unity: $$ x^9-1 = (x-1)\cdot \Phi_{3}(x)\cdot\Phi_9(x) \tag{2}$$ $\mathbb{F}_{121}^*$ is a cyclic group with $120$ elements, hence $x^3-1$ splits as a product of linear factors over $\mathbb{F}_{121}$, but no root of $\Phi_9(x)$ (i.e. no primitive ninth root of unity) lies in $\mathbb{F}_{121}$, since $9\nmid 120$.
We may notice that by defining $\mathbb{F}_{121}$ as in $(1)$ we have: $$ (z+5)^3 = (z+5)(z^2+10z+25) = (z+5)(2-z+3)=25-z^2=1 \tag{3} $$ hence $1,z+5$ and $(z+5)^2 = 5-z$ are the third roots of unity in $\mathbb{F}_{121}$.

Here I got $z+5$ by computing $(z+a)^3$ for $a=1,2,3,4$ then finally being lucky, but there is no need for trial and error. In general we have $\omega=\frac{-1+\sqrt{-3}}{2}$, but in $\mathbb{F}_{11}$ we have $-3=8$, hence $$\omega = \frac{-1+2\sqrt{2}}{2} = z+5$$ since $z=\sqrt{2}$, roughly speaking.