Field with $125$ elements

Question

I want to construct a field with $125$ elements. My idea is to consider the polynomial ring $\Bbb F_5[x]$. It is enough to find an irreducible polynomial $f\in \Bbb F_5[x]$ of degree $3$ because then $\Bbb F_5[x]/(f)$ is a field with exactly $5^3=125$ elements.

How do I find an irreducible polynomial of degree $3$ in $\Bbb F_5[x]$?

Answer 1

If a cubic polynomial of $\mathbb{F}_5[x]$ is reducible, then it splits into a linear factor and a quadratic factor or into the product of three linear factors. Linear factors are very easy to test for, as $(x-a)$ is a factor of $f$ if and only if $f(a) = 0$.

So you might choose a random degree $3$ polynomial and test for the five possible roots.

For instance, I'm tempted to try $f(x) = x^3 + 2x + 1$. Then $$\begin{align} &f(0) = 1, \\ &f(1) = 4, \\ &f(2) = 8 + 4 + 1 \equiv 3, \\ &f(3) = 27 + 6 + 1 \equiv 4, \\ &f(4) = 64 + 8 + 1 \equiv 3. \end{align}$$

As none of these are zero, $f(x)$ is an irreducible cubic.

---

Note that testing for roots explicitly doesn't work for higher degree polynomials. It is possible that a reducible quartic factors into the product of two quadratics. So though there are no roots, it might still be reducible. However since we know that a reducible cubic has a linear factor, we can test just for the linear factor.

Answer 2

The method given by mixedmath is correct. In the illustration the random polynomial selected turned out to be irreducible. In general you may have to try many random ones before becoming lucky.

Instead of trying something wildly random restrict to those satisfying Eisenstein criterion. (because something that is reducible over integers is not going to help us). As we are working mod 5 let us try prime coefficients less than 5.

Trial 1: $x^3+2x+2$. This polynomial evaluates to zero at 1.

Trial 2: Now let us try $g(x)=x^3+3x+3$. Now $g(0) =1$ $$ g(1)=2$$ $$g(2)=2$$ $$g(3)=4$$ $$g(4)=1$$ So using the same reasoning of mixedmath we arrive at an irreducible polynomial.

Answer 3

@mixedmath @P Vanchinathan

One can generate a field with 125 elements by taking the powers $M^n$ of a certain $3 \times 3$ matrix $M$ with coefficients in $\mathbb{F}_5$ of order 124.

Edit: In order to be explicit, let us consider matrix

$$M = \begin{pmatrix}0&0&1\\2&0&0\\0&1&1 \end{pmatrix}$$

Cayley Hamilton theorem applied to $M$ gives: $M^3=2I_3+M^2 \ \ (1)$.

Let $R$ be the ring of $3 \times 3$ matrices with coefficients in $\mathbb{F}_5$ (with ordinary addition and multiplication of matrices).

The subset $S$ of matrices of the form $aI_3+bM+cM^2$ (for any $a,b,c \in \mathbb{F}_5$) is a subring of $R$ (by application of (1) for the stability by multiplication).

The represention of an element of $S$ under the form $aI+bM+cM^2$ is unique. Otherwise, an identity of the form $aI+bM+cM^2=a'I+b'M+c'M^2$ (where $(a,b,c) \neq (a',b',c')$) would infer the existence a polynomial of degree at most 2 that annihilates matrix $M$, and one can verify that no such "minimal" polynomial exist.

As a consequence $S$ is in bijective correspondance with $\mathbb{F}_5^3$, thus has $5 \times 5 \times 5 = 125 $ elements.

Let us now consider set $S'$ defined as the set of all powers $M^n$ which are clearly elements of $S$ by using iteratively (1)).

In fact $S=S'\cup \{0\}$ (where 0 is the null matrix).

Indeed, on one hand $S'$ is included in $S$ because, by successive applications of (1), one can lower any polynomial in $M$ into an at most degree 2 polynomial. And, on the other hand, one can verify that $M$ has order 124 (it can certainly be be proved using the correspondence between matrices and - irreducible - polynomial through the concept of companion matrix).

Thus $S$=$S'$ minus ${0}$ is a (cyclic) group for multiplication.

Therefore $S$ is a field with 125 elements.

(all this in accordance with the fact that a finite field is commutative, and has a cyclic multiplicative group).

See this reference;

Answer 4

Belatedly, there is a way to "be lucky" here, and not so computational, in an informative way. Namely, of all the polynomials known to humans, the best understood are cyclotomic ones. If a cyclotomic polynomial or a relative can resolve an issue, that's good fortune.

After a moment's fooling around, we observe that the smallest power of $5$ such that $5^n-1$ is divisible by $7$ is $5^6$. That is, $5$ happens to be a "primitive root" mod $7$. Thus, a seventh root of unity $\zeta$ is of degree $6$ over $\mathbb F_5$. That is, the seventh cyclotomic polynomial $x^6+x^5+...+x+1$ is irreducible over $\mathbb F_5$.

The irreducible of $\xi=\zeta+\zeta^{-1}$ over $\mathbb F_5$ is obtained by a standard algebraic manipulation: $$ 0\;=\; \zeta^{-3}\Big(\zeta^6+\ldots+\zeta+1\Big) \;=\; \zeta^3+\zeta^2+\zeta+1+\zeta^{-1}+\zeta^{-2}+\zeta^{-3} $$ $$ \;=\; (\xi^3 - 3\xi) + (\xi^2-2) + 1 \;=\; \xi^3 + \xi^2 - 3\xi - 1 $$ We can use $-3=2$ and $-1=4$ if we like.

So, then, basic Galois theory assures us that $x^3+x^2-3x-1$ is irreducible in $\mathbb F_5[x]$.