How to decompose the polynomial $x^{21} + 1$ into a product of irreducible factors over $\mathbb Z/2\mathbb Z$?

Question

This is a problem from a past abstract algebra exam, the degree $21$ was too high for me to solve it. No Wolfram Mathematica please!

Answer 1

Let $\alpha$ be a primitive root of unity of order $21$. The zeros of your polynomial are $\alpha^j,j=0,1,\ldots,20$, and the factors you are looking for are their minimal polynomials. By Galois theory of finite fields the elements $z$ and $z^2$ share their minimal polynomial. For example the zeros of the minimal polynomial of $\alpha$ are thus $\alpha,\alpha^2,\alpha^4,\alpha^8,\alpha^{16},\alpha^{32}=\alpha^{21+11}=\alpha^{11}.$ The next conjugate would be $\alpha^{64}=\alpha^{3\cdot21+1}=\alpha$, so the list ends there. Doing the same for all the zeros we get the minimal polynomials $$ \begin{aligned} p_1(x)&=(x-\alpha^0)\\ p_2(x)&=(x-\alpha)(x-\alpha^2)(x-\alpha^4)(x-\alpha^8)(x-\alpha^{16})(x-\alpha^{11})\\ p_3(x)&=(x-\alpha^3)(x-\alpha^6)(x-\alpha^{12})\\ p_4(x)&=(x-\alpha^5)(x-\alpha^{10})(x-\alpha^{20})(x-\alpha^{19})(x-\alpha^{17})(x-\alpha^{13})\\ p_5(x)&=(x-\alpha^7)(x-\alpha^{14})\\ p_6(x)&=(x-\alpha^9)(x-\alpha^{18})(x-\alpha^{15}). \end{aligned} $$ There real fun is, of course, to identify these polynomials. At least we now know the degrees of the irreducible factors.

Clearly $p_1(x)=x+1$. Equally clearly $p_5(x)=x^2+x+1=(x^3-1)/(x-1)$, because the zeros of $p_5$ are the cubic roots of unity. Between them the polynomials $p_3(x)$ and $p_6(x)$ have the seventh primitive roots of unity as their zeros, so $p_3$ and $p_5$ are the irreducible cubic factors $$(x^3+x+1)(x^3+x^2+1)=(x^6+x^5+x^4+x^3+x^2+x+1)=(x^7-1)/(x-1).$$ We can't tell which is which, because we didn't specify $\alpha$ fully.

That leaves the degree six factors $p_2(x)$ and $p_4(x)$ of $$ \begin{aligned} p_2(x)p_4(x)=\Phi_{12}(x)&=\frac{(x^{21}-1)(x-1)}{(x^7-1)(x^3-1)}=\frac{x^{14}+x^7+1}{x^2+x+1}=\\ &=x^{12}+x^{11}+x^9+x^8+x^6+x^4+x^3+x+1. \end{aligned} $$ At this point it gets tricky. Assume that $$ p_2(x)=x^6+a_5x^5+a_4x^4+a_3x^3+a_2x^2+a_1x+a_0. $$ We see from the expansion that the constant term here is non-zero, so $a_0=1$. A helpful observation is that the zeros of $p_4(x)$ are the reciprocals of those of $p_2(x)$: $\alpha^{20}=1/\alpha$, $\alpha^{19}=1/\alpha^2$ et cetera. This means that $$ p_4(x)=x^6p_2(\frac1x)=x^6+a_1x^5+a_2x^4+a_3x^3+a_4x^2+a_5x+1.$$ Taking this into account, expanding the (known) product $p_2(x)p_4(x)$, and equating the coefficients of like powers gives us the system of equations $$ \left\{\begin{array}{lcl} a_1+a_5&=&1,\\ a_2+a_4+a_1a_5&=&0,\\ (2a_3+)a_1a_4+a_5a_2&=&1,\\ a_2+a_3a_1+a_2a_4+a_5a_3+a_4&=&1,\\ a_1+a_2a_1+a_3a_2+a_4a_3+a_5a_4+a_5&=&0,\\ (2+)a_1^2+a_2^2+a_3^2+a_4^2+a_5^2&=&1,\\ \end{array}\right. $$ from the coefficients of terms of degrees $11,10,9,8,7$ and $6$. The rest are mirror images of these, and won't help us.

Recalling that all the coefficients $a_i\in\Bbb{F}_2=\{0,1\}$ the first equation tells us that one of $a_1,a_5$ is $0$ and the other is $1$. Because we didn't specify $\alpha$, we can interchange the roles of $\alpha$ and $1/\alpha$ or, equivalently, the minimal polynomials $p_2(x)$ and $p_4(x)$. Thus without loss of generality we can decide that $a_1=1$ and $a_5=0$. Also remember that $a_i^2=a_i$ always. This simplifies the last equation. We are left with $$ \left\{\begin{array}{lcl} a_1&=&1,\\ a_5&=&0,\\ a_2+a_4&=&0,\\ a_4&=&1,\\ a_2+a_3+a_2a_4+a_4&=&1,\\ 1+a_2+a_3a_2+a_4a_3&=&0,\\ 1+a_2+a_3+a_4&=&1,\\ \end{array}\right. $$ The fourth equation tells us that $a_4=1$. Substituting this to the third gives $a_2=1$. Substituting these to the fifth or the last equation gives $a_3=0$. We see that all the equations are satisfied.

Thus $$ p_2(x)p_4(x)=(x^6+x^5+x^4+x^2+1)(x^6+x^4+x^2+x+1). $$

---

If the method of unknown coefficients is troublesome, then you can try the following. Our calculations above show that in the quotient ring $$ R=\Bbb{Z}_2[x]/\langle x^{21}+1\rangle $$ the coset of $e(x)=x+x^2+x^4+x^8+x^{16}+x^{11}$ is an idempotent, i.e. $e(x)^2=e(x)$. This means that $$e(x)^2-e(x)=e(x)[e(x)+1]\equiv0\pmod{x^{21}+1}.$$ With any luck (actually with this `asymmetric' choice of $e(x)$ we don't need any luck) the factors of $x^{21}+1$ will be split between $e(x)$ and $e(x)+1$ in some irregular way. This has the advantage that we can calculate the GCD with the very efficient Euclid's algorithm. I cheated and fired up Mathematica at this point - running Euclid on a pair with degrees 16 and 21 is not my idea of a good time. It spat out $$ \gcd(e(x),x^{21}+1)=d(x):=1+x+x^2+x^4+x^6+x^7+x^8+x^9+x^{11}+x^{13}. $$ Testing with the known lower degree factors gives then easily (back to pencil and paper here - see that $x^7+1\mid e(x)$) $$ d(x)=(x^7+1)(x^6+x^4+x^2+x+1). $$

Answer 2

$$x^{21} + 1 = x^{21} - 1 = (x^7)^3 - 1 = (x^7 - 1)(x^{14} + x^7 + 1) = (x - 1)(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)(x^{14} + x^7 + 1) = (x -1)(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)(x^2 + x + 1)(x^{12} - x^{11} + x^9 - x^8 + x^6 - x^4 + x^3 - x +1)$$

Now: The $2$nd one can be shown to be irreducible in $\mathbb Z[x]$; I don't know about $\frac{\mathbb Z}{2\mathbb Z}[x]$. The $3$rd one can be shown to be irreducible in $\frac{\mathbb Z}{2\mathbb Z}[x]$. Good luck with the last one.