6 votos

Muestran que existe una cantidad infinita de polinomios reducibles de la forma $x^n+x+1$ $\mathbf{F}_2$

Aquí es una cuestión de un viejo examen:


Demostrar que existen infinitos $n\in \mathbf{N}, A= x^{n}+x+1 $, que es reducible $\mathbf{F}_{2}[x]$.


El uso de André Nicolás' y Qiaochu del Yuan sugerencia: $x^{2}+x+1$ como dividir el polinomio. $x^{2}+x+1$ es irreducible sobre $\mathbf{F_{2}}$. Si un polinomio irreducible divide a otro polinomio que no es en sí, lo que significa que el polinomio debe ser reducible. Queremos mostrar que $x^{2}+x+1$ divide a todos los polinomios de la forma $x^{3n+5}+x+1$. No puedo calcular la inducción pasos, pero en $\mathbf{F_{2}}$ el polinomio pertenece a la clase de residuo $\tilde{1}$, por lo tanto, no debe ser un infnite cantidad de ellos.

Sobre Gerry Myerson la sugerencia, ¿cómo puedo utilizar la raíz cubica en $\mathbf{F_{2}}$, no necesito $\mathbf{R}[i]$ para que?

La ayuda es muy apreciada.

9voto

Drealmer Puntos 2284

Como una variación en las ideas (esencialmente equivalentes) en las respuestas y comentarios: podríamos preguntarnos que hay ser $\alpha\in \mathbb F_4$resolver $x^n+x+1=0$, señalando que sin duda no hay solución en $\mathbb F_2$. $\alpha\in \mathbb F_4$, $\alpha^4=\alpha$ Y desde $\alpha\not=0,1$, también $\alpha^3=1$ y $\alpha^2+\alpha+1=0$. Por lo tanto, $$ \alpha^{3N+2} \alpha + 1 = \alpha^2+\alpha+1 = 0 $$ Por lo tanto, divide a $x^2+x+1$ $x^{3n+2}+x+1$.

6voto

Bill Cook Puntos 17167

Prueba por inducción.

Base caja ($n=0$): $$\begin{align} (x^2+x+1)\left(x^3+\sum\limits_{i=0}^0 (x^{3i}+x^{3i+2})\right)&=(x^2+x+1)(x^3+x^2+1)\\&=x^5+2x^4+2x^3+2x^2+x+1\\&=x^5+x+1=x^{3(0)+5}+x+1 \end{align}$$ (working in $\mathbb{F}_2[x]$).

Hipótesis inductiva ($n \geq 0$): Supongamos que $$(x^2+x+1)\left(x^{3(n+1)}+\sum\limits_{i=0}^n (x^{3i}+x^{3i+2})\right)=x^{3n+5}+x+1$ $

Entonces: $$\begin{align} &(x^2+x+1)\left(x^{3(n+2)}+\sum\limits_{i=0}^{n+1} (x^{3i}+x^{3i+2})\right)=\\ &(x^2+x+1)\left(x^{3(n+2)}+x^{3(n+1)}+x^{3(n+1)+2}+\sum\limits_{i=0}^{n} (x^{3i}+x^{3i+2})\right)=\\ &(x^2+x+1)(x^{3(n+2)}+x^{3(n+1)+2}) + (x^2+x+1)\left(x^{3(n+1)}+\sum\limits_{i=0}^{n} (x^{3i}+x^{3i+2})\right) \end {Alinee el} $$

con nuestra hipótesis inductiva obtenemos

$$\begin{align} &=(x^2+x+1)(x^{3(n+2)}+x^{3(n+1)+2}) + x^{3n+5}+x+1\\ &=(x^2+x+1)(x^{3n+6}+x^{3n+5}) + x^{3n+5}+x+1\\ &=x^{3n+8}+2x^{3n+7}+2x^{3n+6}+2x^{3n+5}+x+1\\ &=x^{3(n+1)+5}+x+1 \end {Alinee el} $$

Por lo tanto, es reducible en $x^{3(n+1)+5}+x+1$ (o en un anillo de polinomio con coeficientes en un campo de característica 2) $\mathbb{F}_2[x]$ para todos números enteros no negativos $n$.

i-Ciencias.com

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.

Powered by:

X