He visto que $x^{2}+x+1$ $x^{4}+x+1$ son irreducibles sobre$\mathbb{Z}_2$, y pensé que un polinomio de la forma $x^{2^m}+x+1$ $m\ge3$ sería irreductible. Sin embargo el uso de WolframAlpha, mi corazonada estaba equivocado. Podría ser un factor más de $\mathbb{Z}_2$. WolframAlpha sólo podía generar los factores de $m=3,\ldots, 13$ y hasta ahora, he observado que por extraño $m$, mi polinomio es divisible por $x^{2}+x+1$.
Quiero ver cómo se puede demostrar que $x^{2^m}+x+1$ $m\ge3$ es reducible.
Voy a escribir $\mathbb F_2$ en lugar de $\mathbb Z_2$; aquí el $\mathbb F$ es sinónimo de "campo finito" y el subíndice es el número de elementos en el campo finito. Esta notación es conveniente cuando uno desea considerar de mayor tamaño finito de los campos, como yo en esta respuesta.
El polinomio $x^2 + x + 1$ divisiones en el campo de $\mathbb F_4$ $4$ elementos; sus dos raíces son los dos elementos de la $\mathbb F_4$ que no están en $\mathbb F_2$. Ahora si $\alpha \in \mathbb F_4$$\alpha^4 = \alpha$. Por lo tanto si $n = 2 m + 1 $ es impar, tenemos que $$\alpha^{2^{2m + 1}} = (\alpha^{4^m})^2 = \alpha^2,$$ y así $$\alpha^{2^{2m+1}} + \alpha + 1 = 0.$$ En consecuencia, cada una de las dos raíces de la $x^2 + x + 1$ también es una raíz de $x^{2^{2m+1}} + x + 1$ , lo que explica por qué la $x^2 + x + 1$ divide $x^{2^{2m + 1}} + x + 1.$
Para manejar el caso general de los $x^{2^n} + x + 1$ (es decir, el caso de al $n$ no es necesariamente impar) ayuda a recordar algunos Galois de la teoría de campos finitos. El hecho clave es que si $\alpha$ se encuentra en cualquier finito campo de la extensión de $\mathbb F_2$, es decir, algunos $\mathbb F_{2^f}$ algunos $f \geq 1$, entonces el algebraicas conjugados de $\alpha$ son todos de la forma $\alpha, \alpha^2,\alpha^4, \ldots.$ (Esta lista será finito, porque --- asumiendo que elegí $f$ mínimamente --- luego $\alpha^{2^{f-1}} \neq \alpha,$ pero $\alpha^{2^f} = \alpha$, y por lo $\alpha$ tiene exactamente $f$ distintos conjugados $\mathbb F_2$.)
Ahora supongamos que $\alpha$ satisface $$\alpha^{2^n} + \alpha + 1 = 0.$$ La adición de $\alpha + 1$ a ambos lados (y recordando que $ 1 = - 1$ porque en característicos $2$) encontramos que $$\alpha^{2^n} = \alpha+1.$$ Por lo tanto $$\alpha^{2^{2n}} = (\alpha^{2^n})^{2^n} = (\alpha + 1)^{2^n} = \alpha^{2^n} + 1 = (\alpha +1)+1 = \alpha$$ (el uso de los hechos de que $(a+b)^2 = a^2 + b^2$$1 + 1 = 0$, que tienen una característica en $2$).
Así, vemos que la "$f$ " $\alpha$ es en la mayoría de las $2n$, es decir, $\alpha$ tiene más de $2n$ distintos algebraicas conjugados $\mathbb F_2$, por lo que su polinomio mínimo de más de $\mathbb F_2$ tiene un grado en la mayoría de las $2n$. Desde $\alpha$ es una raíz de $x^{2^n} + x + 1$, esta mínima polinomio se divide $x^{2^n} + x + 1$. Si $n \geq 3$, luego $2n$ es estrictamente menor que $2^n$, por lo que este polinomio mínimo de a $\alpha$ también tiene el grado estrictamente menor que el de $x^{2^n} + x + 1$. Así, cuando el $n \geq 3,$ el polinomio $x^{2^n} + x + 1$ debe ser reducible.
Me gustaría presentar una solución que es completamente diferente a la de Matt E del método. El punto de partida es la observación numérica (que he encontrado con el PARI) que cuando el factor de $x^{2^n} + x + 1$ ${\mathbf F}_2[x]$ el número de irreductible factores que se producen por $n = 1, 2, 3,...,11$ es $$ 1, 1, 2, 2, 4, 6, 10, 16, 30, 52, 94. $$ Lo sorprendente acerca de los números y la segunda es que todos ellos son incluso. La lección aquí es que cuando se busca en datos para entender por qué estos polinomios se suele reducible, usted debe no sólo han estado buscando un poco de "obvio" irreductible factor, sino también en el número de factores irreducibles. Sin mostrar que no hay ninguna "obvio" irreductible factor voy a explicar por qué, para $n \geq 3$, $x^{2^n} + x + 1$ debe tener un número par de factores irreducibles en ${\mathbf F}_2[x]$. Que mostrará este polinomio es reducible en ${\mathbf F}_2[x]$, ya que un polinomio irreducible tiene sólo un factor irreducible.
En la escuela primaria de la teoría de números, no es una función estándar que cuenta la paridad del número de factores primos de un número entero positivo. Se llama la función de Möbius y se define como sigue: para un entero positivo $N$, $$ \mu(N) = \begin{cases} 0, & \text{ if } N \text{ has a multiple prime factor}, \\ (-1)^r, &\text{ if } N = p_1\cdots p_r \text{ where the } p_i\text{'s} \text{ are distinct primes}. \end{casos} $$ Por lo $\mu(N) = 1$ si $N$ es un producto de un número par de los distintos números primos (en particular, $\mu(1) = 1$$r = 0$) y $\mu(N) = -1$ si $N$ es un producto de un número impar de distintos números primos, mientras que $\mu(N) = 0$ si hay algún factor principal de $N$ aparezca más de una vez (por ejemplo, $\mu(12) = 0$ desde el 2 es un factor de 12 veces). Por lo que la función de Möbius en realidad sólo cuenta la paridad del número de factores primos de squarefree enteros positivos. Para cualquier prime $p$, $\mu(p) = -1$. Por lo tanto, si $\mu(N) = 1$ $N$ definitivamente no es un número primo.
La captura con la función de Möbius es que no se conoce ninguna manera de averiguar lo $\mu(N)$ es esencialmente sin factoring $N$. Bien, para estar en el lado seguro, permítanme decir que si conocemos $N$ es squarefree, por lo $\mu(N) = \pm 1$,, a continuación, averiguar si $\mu(N)$ $1$ o $-1$ no puede hacerse sin tener $N$. Sencillamente, no hay ninguna fórmula para $\mu(N)$ otros de su definición. (Por supuesto, si usted no ha visto la función de Möbius antes, luego otra cosa es que se ve como un completo loco función. Por qué es importante? La razón es la Möbius de la inversión de la fórmula, en la que la función de Möbius juega un papel destacado. Una de sus consecuencias es que el inverso multiplicativo de la de Riemann zeta función de $\zeta(s) = \sum_{N \geq 1} 1/N^s$$\sum_{N \geq 1} \mu(N)/N^s$, por lo que la función de Möbius surge de forma natural si desea escribir $1/\zeta(s)$ como una de Dirichlet de la serie).
Hay una gran cantidad de analogías entre las ${\mathbf Z}$${\mathbf F}_p[x]$, para el primer $p$, y, en particular, podemos definir una función de Möbius en monic polinomios en ${\mathbf F}_p[x]$. (Creo que de monic polinomios como análoga a los enteros positivos.) Para cualquier monic $f(x)$${\mathbf F}_p[x]$, $$ \mu(f) = \begin{cases} 0, & \text{ if } f \text{ has a multiple irreducible factor}, \\ (-1)^r, & \text{ if } f = \pi_1\cdots\pi_r \text{ where the } \pi_i\text{'s} \text{ are distinct monic irreducibles}. \end{casos} $$ Por ejemplo, $\mu(\pi) = -1$ al $\pi$ es irreductible, por lo $\mu(x+c) = -1$ para cualquier constante$c$${\mathbf F}_p$. Tenga en cuenta que, como con la clásica función de Möbius, $\mu(f)$ nos cuenta la paridad del número de monic irreductible factores de $f$ al $f$ es squarefree. Pero hay una enorme diferencia entre el ${\mathbf Z}$ ${\mathbf F}_p[x]$ cuando se trata de determinar que algo es squarefree, porque no es un método para determinar que un polinomio en ${\mathbf F}_p[x]$ es squarefree sin la factorización es: $f(x)$ es squarefree iff $f(x)$ $f'(x)$ son relativamente primos. Tenga en cuenta que se squarefree en ${\mathbf F}_p[x]$ es la misma cosa que ser separables (no varias raíces), que vincula esto con más estándar de los conceptos de la teoría de campo de polinomios.
Ejemplo. En ${\mathbf F}_2[x]$, $x^{2^n}+x+1$ es squarefree desde su derivada es $1$, que es sin duda relativamente privilegiada para el polinomio original.
Lo realmente sorprendente es que es posible calcular $\mu(f)$ sin factor de $f$.
Teorema. Si $p$ es una extraña prime, a continuación, $\mu(f) = (-1)^{\deg(f)}(\frac{\text{disc}(f)}{p})$ donde $(\frac{\cdot}{p})$ es el símbolo de Legendre y $\text{disc}(f)$ es el discriminante de $f(x)$. Si $p = 2$ $f(x)$ es squarefree en ${\mathbf F}_2[x]$, vamos a $F(x)$ ser un monic levantamiento de $f(x)$${\mathbf Z}[x]$. A continuación, $\mu(f) = 1$ si $\text{disc}(F) \equiv 1 \bmod 8$ $\mu(f) = -1$ si $\text{disc}(F) \equiv 5 \bmod 8$.
Es un teorema de Stickelberger que un monic polinomio en ${\mathbf Z}[x]$ con impar discriminante debe tener discriminante que es $1 \bmod 4$, por lo que mod 8 el discriminante es 1 o 5.
No voy a probar el teorema de aquí, pero yo voy a decir algunos antecedentes. Este teorema es debido a la Bolita (1878) al $p$ es impar. El caso de $p=2$ fue dado por Stickelberger en un corto papel en la primera ICM en 1897 y Swan fue redescubierta en 1962 (Pacífico J. Matemáticas) en términos de una elevación de ${\mathbf F}_2$ a los 2-ádico enteros en lugar de ${\mathbf Z}$. La prueba para que la extraño $p$ necesidades de Galois, teoría de campos finitos, pero para $p = 2$ se requiere más trabajo. Debo señalar que de Pellets, Stickelberger, y el Cisne no estaban pensando directamente en términos de una función de Möbius en polinomios sobre un campo finito. Por ejemplo, Pellet y Stickelberger escribió la fórmula con el discriminante plazo en un lado y el resto en el otro lado con la Möbius valor que aparece como un poder de $-1$: eran el estudio de la "cuadrática" la naturaleza de la discriminante de un polinomio de mod $p$ cuando el discriminante de mod $p$ es distinto de cero. (La fórmula del teorema es trivial cuando el discriminante es 0, ya que ambos lados son 0, pero P, S, y S no escribir la fórmula en ese caso ya que no tiene ningún interés para ellos.)
Para hacer los cálculos con este teorema, permítanme recordar una de las definiciones del discriminante de una monic polinomio $h(x)$ grado $d$ sobre un campo: $\text{disc}(h) = (-1)^{d(d-1)/2}\prod_{i=1}^d h'(r_i)$ donde $h(x) = \prod_{i=1}^d (x-r_i)$ en la división de campo. En particular, la nota $(-1)^{d(d-1)/2} = 1$ al $d$ es un múltiplo de 4.
Ahora es el momento para volver a la pregunta original. Vamos a aplicar este teorema a su polinomio $x^{2^n} + x + 1$${\mathbf F}_2[x]$, mostrando a $\mu(x^{2^n} + x + 1) = 1$ cualquier $n \geq 3$ donde $\mu$ es la función de Möbius en ${\mathbf F}_2[x]$. Primero observar que en la característica 2, $x^{2^n} + x + 1 = (x+1)^{2^n} + x$.
Teorema. Para cualquier polinomio no constante $g(x)$ en ${\mathbf F}_2[x]$, $\mu(g^8 + x) = 1$.
La conclusión de este teorema es falso cuando $g$ es constante, y vamos a ver pronto en la prueba de la $g$ no constante asuntos: significa que el grado de $g^8+x$ está determinado por la $g^8$ parte y no la $x$ part.
La prueba del teorema: Vamos a $G(x)$ ${\mathbf Z}[x]$ ser cualquier monic levantamiento de $g(x)$. (Por ejemplo, cada mod 2 coeficiente de $g(x)$, que es de 0 o 1 mod 2 podrían ser reemplazados con los números enteros de 0 o 1.) A continuación,$\deg(G) = \deg(g) \geq 1$, lo $G^8 + x$ tiene el grado $8\deg(G)$, que es un múltiplo de 8. Ese es el paso que se requiere $g$, y, por tanto,$G$, a no constante. Y la derivada de $G^8 + x$$8G^7G' + 1$, por lo que si dejamos $r_1,\dots,r_D$ ser las raíces de $G^8 + x$, lo $D$ es un múltiplo de 8, $$ \text{disc}(G^8 + x) = \prod_{i=1}^D (1 + 8G(r_i)^7 G'(r_i)). $$ Desde $G^8 + x$ es monic , sus raíces son algebraica de los números enteros, por lo que el número de la derecha es un producto de enteros algebraicos que son todos los 1 y 8 veces un entero algebraico. Por lo tanto, su producto es 1 más de 8 veces un entero algebraico. Puesto que el lado izquierdo $\text{disc}(G^8 + x)$${\mathbf Z}$, el número de la izquierda debe ser $1 \bmod 8$, por lo que por el Möbius fórmula en ${\mathbf F}_2[x]$, $\mu(g^8 + x) = 1$. QED
Cuando $n \geq 3$, $2^n$ es un múltiplo de 8 y $(x+1)^{2^n} + x = g^8 + x$$g(x) = (x+1)^{2^{n-3}}$, por lo que este teorema implica $x^{2^n} + x + 1$ es reducible ${\mathbf F}_2$ porque hemos demostrado que tiene un número par de factores irreducibles. Mientras Matt E la solución es mucho más corta que la mía, y es una agradable aplicación de la teoría de Galois de campos finitos (voy a tener que recordar para la próxima vez que me enseñe una teoría de Galois, por supuesto), observe que el teorema anterior es mucho más general resultado: $g^8 + x$ es reducible para cualquier no constante $g$ ${\mathbf F}_2[x]$ porque tiene un número par de factores irreducibles.
Hay un análogo de este en todas las características: para cualquier prime $p$, $\mu(g^{4p}+x) = 1$ para todos no constante $g(x)$${\mathbf F}_p[x]$.
Dos ajustes de donde esta Möbius fórmula fue aplicada algo recientemente se describen en http://www.math.uconn.edu/~kconrad/artículos/texel.pdf.
Es cierto que para $n\geq 3$ $x^{2^n}+x+1$ es reducible. Sólo podía hacerlo el extraño caso ahora, tal vez voy a hacer el otro caso, más tarde. Espero no incurrir en ninguna equivocación: yo creo que para impar n: $$x^{2^n}+x+1 = (x^{2^n-2}+x^{2^n-3}+x^{2^n-5}+x^{2^n-6}+\ldots + x^3+x^2+1)\cdot(x^2+x+1)$$
En la parte izquierda del polinomio de la derecha he dejado de lado todo el $x^{2^n-i}$ $i\equiv 1$ mod 3. Desde $2^n\equiv 2$ mod 3 (n impar) que el polinomio termina con $\ldots+x^3+x^2+1$. Estamos trabajando en $\mathbb{Z}_2$, por lo que es bastante fácil de comprobar esta afirmación.
He aquí otra respuesta parcial:
Si puedo hacer los cálculos en $GF_2[x]\mod x^4+x+1$ y, a continuación, $$ x^{2^m} = (x^4)^{2^{m-2}} = (x+1)^{2^{m-2}} = x^{2^{m-2}}+1 $$ Por lo tanto, si dejo $m = 2n$$x^{2^m} = x^{2^0} + n = x + n$, Ahora si $n$ es impar, entonces $x+n + x+1 = 0$ sobre GF(2).
En otras palabras, cuando se $m\equiv 2\pmod 4$ (debido a $m = 2n$ $n$ impar), el polinomio tiene $x^4+x+1$ como un factor.
-- edit. Permítanme reformular la factorización por Michalis N en esta práctica el idioma. Más de $GF_2[x] \mod x^2 + x+1$ es cierto que $$ x^{2^m} = (x^2)^{2^{m-1}} = (x+1)^{2^{m-1}} = x^{2^{m-1}} + 1$$ Por lo tanto, si $m$ es impar, a continuación, $x^{2^m} = x+1$ y, por tanto,$x^{2^m}+x+1 = 0$. En otras palabras $x^{2^m}+x+1$ $x^2+x+1$ como un factor.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
