Cómo descomponer el polinomio $x^{21} + 1$ en un producto de factores irreducibles sobre $\mathbb Z/2\mathbb Z$ ?

Question

Este es un problema de un examen pasado de álgebra abstracta, el grado $21$ era demasiado alto para que lo resolviera. ¡No hay Wolfram Mathematica por favor!

Answer 1

Dejemos que $\alpha$ sea una raíz primitiva de la unidad de orden $21$ . Los ceros de su polinomio son $\alpha^j,j=0,1,\ldots,20$ y los factores que buscas son sus polinomios mínimos. Por la teoría de Galois de los campos finitos los elementos $z$ y $z^2$ comparten su polinomio mínimo. Por ejemplo, los ceros del polinomio mínimo de $\alpha$ son por lo tanto $\alpha,\alpha^2,\alpha^4,\alpha^8,\alpha^{16},\alpha^{32}=\alpha^{21+11}=\alpha^{11}.$ El siguiente conjugado sería $\alpha^{64}=\alpha^{3\cdot21+1}=\alpha$ Así que la lista termina ahí. Haciendo lo mismo para todos los ceros obtenemos los polinomios mínimos $$ \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} $$ Lo realmente divertido es, por supuesto, identificar estos polinomios. Al menos ahora sabemos los grados de los factores irreducibles.

Claramente $p_0(x)=x+1$ . De forma igualmente clara $p_5(x)=x^2+x+1=(x^3-1)/(x-1)$ porque los ceros de $p_5$ son raíces cúbicas de la unidad. Entre ellos los polinomios $p_3(x)$ y $p_6(x)$ tienen como ceros las séptimas raíces primitivas de la unidad, por lo que $p_3$ y $p_5$ son los factores cúbicos irreducibles $$(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).$$ No podemos decir cuál es cuál, porque no especificamos $\alpha$ totalmente.

Eso deja el grado seis factores $p_2(x)$ y $p_4(x)$ de $$ \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} $$ En este punto la cosa se complica. Supongamos que $$ p_2(x)=x^6+a_5x^5+a_4x^4+a_3x^3+a_2x^2+a_1x+a_0. $$ Vemos por la expansión que el término constante aquí es distinto de cero, por lo que $a_0=1$ . Una observación útil es que los ceros de $p_4(x)$ son los recíprocos de los de $p_2(x)$ : $\alpha^{20}=1/\alpha$ , $\alpha^{19}=1/\alpha^2$ etc. Esto significa que $$ p_4(x)=x^6p_2(\frac1x)=x^6+a_1x^5+a_2x^4+a_3x^3+a_4x^2+a_5x+1.$$ Teniendo en cuenta esto, ampliando el producto (conocido) $p_2(x)p_4(x)$ y al igualar los coeficientes de potencias similares se obtiene el sistema de ecuaciones $$ \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. $$ a partir de los coeficientes de los términos de los grados $11,10,9,8,7$ y $6$ . El resto son imágenes especulares de estos, y no nos ayudarán.

Recordando que todos los coeficientes $a_i\in\Bbb{F}_2=\{0,1\}$ la primera ecuación nos dice que uno de $a_1,a_5$ es $0$ y el otro es $1$ . Porque no especificamos $\alpha$ podemos intercambiar los papeles de $\alpha$ y $1/\alpha$ o, de forma equivalente, los polinomios mínimos $p_2(x)$ y $p_4(x)$ . Así, sin pérdida de generalidad, podemos decidir que $a_1=1$ y $a_5=0$ . Recuerde también que $a_i^2=a_i$ siempre. Esto simplifica la última ecuación. Nos queda $$ \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. $$ La cuarta ecuación nos dice que $a_4=1$ . Sustituyendo esto a la tercera da $a_2=1$ . Sustituyendo esto en la quinta o última ecuación se obtiene $a_3=0$ . Vemos que todas las ecuaciones se satisfacen.

Así, $$ p_2(x)p_4(x)=(x^6+x^5+x^4+x^2+1)(x^6+x^4+x^2+x+1). $$

---

Si el método de los coeficientes desconocidos es problemático, puedes probar lo siguiente. Nuestros cálculos anteriores muestran que en el anillo de cocientes $$ R=\Bbb{Z}_2[x]/\langle x^{21}+1\rangle $$ el coset de $e(x)=x+x^2+x^4+x^8+x^{16}+x^{11}$ es un idempotente, es decir $e(x)^2=e(x)$ . Esto significa que $$e(x)^2-e(x)=e(x)[e(x)+1]\equiv0\pmod{x^{21}+1}.$$ Con un poco de suerte (en realidad con esta elección "asimétrica" de $e(x)$ no necesitamos ninguna suerte) los factores de $x^{21}+1$ se repartirá entre $e(x)$ y $e(x)+1$ de forma irregular. Esto tiene la ventaja de que podemos calcular el GCD con el eficacísimo algoritmo de Euclides. Hice trampa y encendí Mathematica en este punto -ejecutar Euclides en un par con grados 16 y 21 no es mi idea de un buen momento. Escupió $$ \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}. $$ La prueba con los factores de grado inferior conocidos da entonces fácilmente (volver al lápiz y al papel aquí - ver que $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)$$

Ahora: El $2$ ndo se puede demostrar que es irreducible en $\mathbb Z[x]$ ; no sé sobre $\frac{\mathbb Z}{2\mathbb Z}[x]$ . El $3$ rd puede demostrarse que es irreducible en $\frac{\mathbb Z}{2\mathbb Z}[x]$ . Buena suerte con el último.