# Find roots of polynomial in a finite field

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?

• So far mostly good. Presumably $\alpha$ is the coset $x+\langle h(x)\rangle$. Therefore you can simply state that $L=\{k\alpha+b, k,b\in\Bbb{Z}_{11}\}$. Irreducibility of $h(x)$ is all you need to get this far. Observe that $h(\alpha)=0$ so there is no need to add that term. Seeing that $1,\alpha$ and $\alpha^2$ are the only zeros of $g$ in $L$ is a bit more involved. I endorse lhf's method. Had I been awake when you posted this question I would have given the same answer :-) Jun 26 '16 at 6:46

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.

• Where did you get $(z+5)^3$ from? Jun 25 '16 at 21:00
• @Levitan: by trial and error. I computed $(z+a)^3$ for $a=1,2,3,4$ and finally got lucky. Jun 25 '16 at 21:01
• @Levitan: anyway, there is a way that avoids 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. Answer updated with this explanation. Jun 25 '16 at 21:03
• $\sqrt{2} \notin Z_{11}$ Jun 26 '16 at 8:50
• @Levitan: I know that, but $z$ in $\mathbb{F}_{11}[z]/(z^2-2)$ is still a root of $z^2=2$. So we may say that $\sqrt{2}\not\in\mathbb{F}_{11}$, but $\sqrt{2}\in\mathbb{F}_{121}$. Jun 26 '16 at 12:03

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$.

• could you please point me to the theory which gives "$x^9=1$ equal to $x^3=1$ because of $gcd(120,9)=3$"? This statement is not clear for me. From where you got $u^{40}$, $u^{80}$ is also not clear Jun 26 '16 at 8:56
• @Levitan, $x^{120}=1$ because of Lagrange's theorem. Now write $3=120a+9b$ and conclude $x^3=1$. For the second part, $v=u^{120/3}$ has order $3$ and so does $v^2$.
– lhf
Jun 26 '16 at 11:51