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]$?

  • $\begingroup$ You can get the field with $p^n$ elements as splitting field of $t^{p^n}-t\in \mathbb{F}_p[t]$. $\endgroup$ – user302982 Jul 24 '16 at 8:20
  • $\begingroup$ Thanks. Why is that thing irreducible? $\endgroup$ – MyNameIs Jul 24 '16 at 8:21
  • 2
    $\begingroup$ The best idea is to do trial and error. It's easy to check whether a degree 3 polynomial is irreducible, because you only need to check whether it has a root. $\endgroup$ – Wojowu Jul 24 '16 at 8:21
  • 1
    $\begingroup$ My polynom isn't irreducible, but I thought you are also interested in how to get the finite fields and you can realize them as splitting fields. $\endgroup$ – user302982 Jul 24 '16 at 8:24

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.

  • 1
    $\begingroup$ This is great, thank you! $\endgroup$ – MyNameIs Jul 24 '16 at 8:35

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.


@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;

  • 2
    $\begingroup$ First, don't you need the matrix to have order 124? Second, doesn't this just change the original question ("how do I find an irreducible polynomial of degree 3") to the (seemingly much more difficult) question of how to find a $3\times3$ matrix of order 124? $\endgroup$ – Morgan Rodgers Jul 24 '16 at 10:37
  • $\begingroup$ @JeanMarie: An extension field $K$ of degree $n$ over a field $F$ can be realised as an $F$-subalgebra of $M_{n\times n}(F)$. When $F$ is a finite field, $K^*$ will be a torsion subgroup of $GL_n(F)$. Is this what you mean by Wedderburn theorem? $\endgroup$ – P Vanchinathan Jul 24 '16 at 11:28
  • $\begingroup$ @Morgan Rodgers 1) You are right, this matrix is of order 124. 2) I dont agree : I answer to the initial question "I want to construct a field with 125 elements" but using a different "idea". Moreover, I thought it was useful to speak about this construction process that is a little less publicized than the method using irreducible polynomials 3) I dont think it is more difficult (I could have taken a companion matrix which is completely equivalent to finding an irreducible polynomial). $\endgroup$ – Jean Marie Jul 24 '16 at 12:18
  • $\begingroup$ @P Vanchinathan Thank you very much. In fact, I used the name "Wedderburn" without checking. And now, I see that it deals with commutativity of finite fields. What I needed is a different result (I have re-written it in my answer), i.e., that the mutiplicative group of a finite field is cyclic (there are broader results). $\endgroup$ – Jean Marie Jul 24 '16 at 12:31
  • $\begingroup$ @JeanMarie But my point is, you still need to have the answer to the original question (how to find an irreducible polynomial) to have an effective way to obtain this matrix. Instead you seem to pull it out of thin air. Maybe if you show how to obtain this matrix, this can be seen to answer the OPs question. $\endgroup$ – Morgan Rodgers Jul 24 '16 at 12:34

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.