# Counting the roots of a polynomial over a finite field

Let $\mathbb{F}_{11}$ be the field of 11 elements and let $\mathcal{K}$ be the splitting field of $x^{3} - 1$ over $\mathbb{F}_{11}$. How many roots does $(x^{2} - 3)(x^{3} - 3)$ have in $\mathcal{K}$?

First, note that $x^{3} - 1 = (x- 1)(x^{2} + x + 1)$ and the quadratic factor is irreducible over $\mathbb{F}_{11}$ so that $\mathcal{K} = \mathbb{F}_{11}/(x^{2} + x + 1) \cong \mathbb{F}_{11^{2}}$.

Note that $3^{6} = 3$ in $\mathbb{F}_{11^{2}}$ so that $(x^{2} - 3)(x^{3} - 3) = (x - 27)(x+ 27)(x-9)(x^{2} + 9x + 81)$, so that the number of roots of the given polynomial in $\mathbb{F}_{11^{2}}$ is three ( I am not even sure if the quadratic factor in this decomposition does not actually have a root).

Is there a general method for determining the roots of say $(x^{n} - a)$ over a finite field of $p^{m}$ elements?

I was thinking: Find the smallest positive integer k for which $a^{k} = 1$, then $a = x^{n} \implies 1 = a^{k} = x^{kn}$, which is an equation in the cyclic group of cardinality $p^{m} -1$, hence the number of such solutions has to be the $\gcd(kn, p^{m} -1)$. This does not seem correct.

• The quadratic factor $p(x)=x^2+9x+81$ splits, too. Just notice that $p(9x)=81(x^2+x+1)$. – Jack D'Aurizio Aug 20 '14 at 23:20
• I do not see the factorization of the resultant quadratic in your comment into linear factors. – akech Aug 21 '14 at 2:13
• You defined $\mathcal{K}$ as the splitting field of $x^2+x+1$, so surely $x^2+x+1$ splits into linear factors over $\mathcal{K}$. – Jyrki Lahtonen Aug 21 '14 at 4:23
• As you now understand the situation, let me encourage you to write up your understanding, and then post it as an answer to your question. – Gerry Myerson Aug 21 '14 at 10:24
• Seconding Gerry's suggestion. A wonderful opportunity to get more feedback. Free of charge! No risk for humiliation in front of your professor and/or peers! – Jyrki Lahtonen Aug 22 '14 at 17:04

First, note that $x^{3} - 1 = (x- 1)(x^{2} + x + 1)$ and the quadratic factor is irreducible over $\mathbb{F}_{11}$ so that $\mathcal{K} = \mathbb{F}_{11}/(x^{2} + x + 1) \cong \mathbb{F}_{11^{2}}$.

Note that $3^{6} = 3$ in $\mathbb{F}_{11^{2}}$ so that $(x^{2} - 3)(x^{3} - 3) = (x - 27)(x+ 27)(x-9)(x^{2} + 9x + 81)$.

As suggested in the comments, $p(x) = x^{2} + 9x + 81$ splits into linear factors because $p(9x) = 81(x^{2} + x + 1) = 81(x - \zeta_{3})(x - \overline{\zeta_{3}})$. So that $p(x) = 9(x - 9\zeta_{3})(x - 9\overline{\zeta_{3}})$ in $\mathcal{K} = \mathbb{F}_{11}(\zeta_{3})$ Therefore, $(x^{2} - 3)(x^{3} - 3)$ has five roots in $\mathcal{K}$.