Factor $x^5+x^4+x^3+x^2+x+1$ over $\Bbb F_5$

Question

This is the polynomial with roots $\omega,\omega^2,...,\omega^5$, where $\omega$ is the primitive $6^{th}$ root of unity over $\Bbb F_5$. So that the irreducible factors are the minimal polynomials of the roots, and using the Galois automorphism $\sigma(\omega)=\omega^5$, one can find out that the irreducible factors are $(x-\omega^3)$, $(x-\omega^2)(x-\omega^4)=x^2-(\omega^2+\omega^4)x+1$ and $(x-\omega)(x-\omega^5) = x^2-(\omega+\omega^5)x+1.$

As $(\omega^3)^2=1$ while $\omega^3\neq 1$, $\omega^3=-1$. But I have trouble finding $\omega^2+\omega^4=-(\omega^{-1}+\omega)$ and $\omega+\omega^5=\omega^{-1}+\omega$. The key is to find $\omega^{-1}+\omega$ in this case.

In general, let $n$ such that the prime $p$ doesn't divide $n$, then over the finite field $\Bbb F_{p^m}$ one could find minimal polynomial of each $\omega^k$, where $\omega$ is the primitive $n^{th}$ root of unity in the form $(x-\omega^k)(x-\omega^{kp^m})...$ but then the problem is to compute the coefficient now as an element in $\Bbb F_{p^m}$. Is there a general way to compute them?

Answer 1

Using computer support, there is not too much to do. For instance, asking sage...

sage: F = GF(5)
sage: R.<x> = PolynomialRing(F)
sage: f = x^5 + x^4 + x^3 + x^2 + x + 1
sage: f.factor()
(x + 1) * (x^2 + x + 1) * (x^2 + 4*x + 1)

The human way would be as follows. We factor instead $x^6-1$. Over the integers we know the factors $(x-1)$, $(x^2-1)$, and $(x^3\pm 1)$. So the given polynomial $f$ (lifted or not from $\Bbb Z/5=\Bbb F_5$ to the integers $\Bbb Z$) has the factors $(x+1)$, and $(x^2+x+1)$, and $(x^2-x+1)$.

We can check that the two factors of degree two are irreducible over the field with five elements $\Bbb Z/5=\Bbb F_5$, they have no root in this field. So the computer decomposition is also easy to get with bare hands.

---

In a more general case we still can use the Galois structure of the finite fields. For illustration, let us consider the prime $p=101$, the exponent $k=3$, and the prime power $q=p^k=101^3$ of this prime, and the fields $F=\Bbb F_p=\Bbb Z/p$, and $L=\Bbb F_q$, and some few polynomials of the shape $x^n-1$ with $n$ relatively prime to $p$. First of all, this polynomial factors over $\Bbb Z$ as $$ x^n-1 =\prod_{d\text{ divisor of }n}\Phi(d)(x)\ , $$ where $\Phi_d$ is the $d$.th cyclotomic polynomial.

So we want to factor some $\Phi_d$, seen as polynomial in $L=\Bbb F_q[x]$. Let $a$ be a root of $\Phi_d$ in an extension of $\Bbb F_q$. Then its Galois conjugates are $a$, $a^q$, $a^{q^2}$, and so on. The polynomial $\Phi_d$ will stay irreducible over $\Bbb F_q$ - as was the case with the factors given polynomial $(x^6-1)/(x-1)=\Phi_2(x)\Phi_3(x)\Phi_6(x)$ over $\Bbb F_5$, if we have again $\varphi(d)$ such conjugates, the same number as over $\Bbb Q$. This is the case when $q$ modulo $d$ has multiplicative order $\phi(d)$ in the multiplicative group $(\Bbb Z/d)^\times$. I.e. $q$ modulo $d$ is a genarator of this multiplicative group.

Else we stop earlier and get earlier factors.

---

---

Some examples illustrate this situation for the sample prime power $q=101^3$. We may realize $L$ as $F[u]:=F[x]/(x^3 + 3x -2)$, and $u$ is the class of $x$ modulo $(x^3 + 3x -2)$.

---

• $n=5$:

  The polynomial $\Phi_5(x)=(x^4+x^3+x^2+x+1)$ splits completely over $F=\Bbb F_p$ (so also over $L=\Bbb F_q$), $\Phi_5(x)=(x-a)(x-a^2)(x-a^3)(x-a^4)$, $a=-6=95$. This can be seen as follows. The multiplicative group $F^\times$ of $F$ is cyclic of order $(p-1)=100$, and $n=5$ is not relatively prime to this order. In fact $n$ divides $(p-1)$, and so we can find a root $a$ of the unit in $F$ which has order $5$. And yes, explicitly, $a=-6$ is such a root, $a^5=-7776=-7777+1=-7070-707+1=1$, and its powers $a^k$, $k=1,2,3,4$ (prime to $5$), are also units of order $5$.

---

• $n=11$:

  The polynomial $\Phi_{11}(x)=(x^{10}+x^9+x^8 + x^7+x^6+x^5+x^4+x^3+x^2+x+1)$ remains irreducible over $F$ and over $L$. Why? The residue class of $q=101^3$ in the multiplicative group $(\Bbb Z/n)^\times$ is $8=-3$, and this element has maximal order $10$.

  Explicitly, modulo eleven $(-3)^5=-243=-242-1=-1\ne 1$, and $(-3)^2=9\ne1$, so the order does not drop from ten. The ten powers of $(-3)$ modulo eleven are $(-3)^1=8$, $(-3)^2=9$, $(-3)^3=-27=-5=6$, and so on.

  The polynomial $\Phi_{11}$ has no root in $F$, and having degree ten, we expect a root in an extension with degree dividing $10$. So there is no root in $L$ either. Take such a root $a$ in an extension of $L$. Its conjugates are $a$, $a^q=a^8$, $a^{q^2}=a^9$, $a^{q^3}=a^6$, and so on. Since $(-3)$ generates $(\Bbb Z/11)^\times$, we have ten conjugates, exactly so many as over $\Bbb Q$. So $\Phi_{11}$ remains irreducible also over

---

• $n=39$:

  The polynomial $\Phi_{39}(x)=(x^{24} - x^{23} + x^{21} - x^{20} + x^{18} - x^{17} + x^{15} - x^{14} + x^{12} - x^{10} + x^{9} - x^{7} + x^{6} - x^{4} + x^{3} - x + 1)$ is a case "between" the above two cases. Let us see what happens over $F=\Bbb F_{101}$. There is no root of $\Phi_{39}$ in $F$. Let $a$ be a root in some extension of $F$ with degree dividing $\varphi(39)=24$. Then the conjugates over $F$ are $a$, $a^p$, $a^{p^2}$, and so on. Because of $a^{39}=1$, we consider the powers that appear $1,p,p^2,$ and so on as elements of $(\Bbb Z/39)^\times\cong(\Bbb Z/2)^\times \times(\Bbb Z/13)^\times$. Then $p=101$ has order six modulo $39$, let us check $101^6$ modulo $13$ for this, $101^3=1030301=103\cdot1000 + 301=-10000+2=-10010+10+2=12=-1$ modulo $13$. So the roots of $\Phi_{39}$ in the splitting field of this polynomial over $\Bbb F_p$ come in four $6$-packs, thus we expect a splitting in four factors of degree six. And this is indeed the case:

    p, q = 101, 101^3
    F = GF(p)
    L.<u> = GF(q)
    RF.<t> = PolynomialRing(F)
    RL.<x> = PolynomialRing(L)
  
    print("Factors over F:")
    for f, mul in RF( cyclotomic_polynomial(39) ).factor():
        print("    ", f)
  
    print(f"Factors over L:")
    for f, mul in RL( cyclotomic_polynomial(39) ).factor():
        print("    ", f)
  

  And we obtain:

    Factors over F:
         t^6 + 16*t^5 + 4*t^4 + 85*t^3 + 4*t^2 + 16*t + 1
         t^6 + 55*t^5 + 31*t^4 + 74*t^3 + 31*t^2 + 55*t + 1
         t^6 + 63*t^5 + 23*t^4 + 39*t^3 + 23*t^2 + 63*t + 1
         t^6 + 67*t^5 + 54*t^4 + 94*t^3 + 54*t^2 + 67*t + 1
    Factors over L:
         x^2 + (77*u^2 + 15*u + 4)*x + 1
         x^2 + (27*u^2 + 24*u + 5)*x + 1
         x^2 + (35*u^2 + 19*u + 8)*x + 1
         x^2 + (28*u^2 + 69*u + 11)*x + 1
         x^2 + (79*u^2 + 2*u + 12)*x + 1
         x^2 + (89*u^2 + 54*u + 15)*x + 1
         x^2 + (5*u^2 + 22*u + 31)*x + 1
         x^2 + (57*u^2 + 33*u + 34)*x + 1
         x^2 + (95*u^2 + 30*u + 44)*x + 1
         x^2 + (98*u^2 + 62*u + 46)*x + 1
         x^2 + (78*u^2 + 28*u + 94)*x + 1
         x^2 + (39*u^2 + 46*u + 99)*x + 1
  

  As seen, over $L$ we have factors of degree two, since $q=101^3$ has order two in $(\Bbb Z/39)^\times$. This information can be obtained using Galois structural considerations. But for the explicit formula of each factor, we have to get wet and compute.

---

• $n=19$:

  The polynomial $\Phi_{19}(x)=(x^{18} + x^{17} + \dots + x + 1)$ shows a similar situation. The number $p$, seen inside $(\Bbb Z/19)^\times$ has order nine, $101^3=7$ and $7^3=1$ modulo $19$, so we expect two factors of degree nine over $F=\Bbb F_p$. The order is three for $q=p^3$, so we expect to see six factors of degree three. Yes, the same code adapted to show $\Phi_{19}$ factorizations delivers:

    Factors over F:
         t^9 + 27*t^8 + 99*t^7 + 76*t^6 + 29*t^5 + 24*t^4 + 73*t^3 + 2*t^2 + 26*t + 100
         t^9 + 75*t^8 + 99*t^7 + 28*t^6 + 77*t^5 + 72*t^4 + 25*t^3 + 2*t^2 + 74*t + 100
    Factors over L:
         x^3 + (49*u + 9)*x^2 + (10*u^2 + 28*u + 96)*x + 100
         x^3 + (91*u^2 + 73*u + 5)*x^2 + (52*u + 92)*x + 100
         x^3 + (43*u^2 + 83*u + 10)*x^2 + (81*u^2 + 55*u + 52)*x + 100
         x^3 + (20*u^2 + 46*u + 49)*x^2 + (58*u^2 + 18*u + 91)*x + 100
         x^3 + (68*u^2 + 46*u + 60)*x^2 + (20*u^2 + 95*u + 31)*x + 100
         x^3 + (81*u^2 + 6*u + 70)*x^2 + (33*u^2 + 55*u + 41)*x + 100
  

  Again, the structure can be obtained by checking the order of $p$, respectively of $q$ in $(\Bbb Z/n)^\times=(\Bbb Z/19)^\times$, but to get the factors explicitly leads to a (less human) computation.