Polinomios sobre GF (7)

Question

El siguiente ejercicio es de Golán, el libro de álgebra lineal.

Problema: Considerar el álgebra de los polinomios de más de $GF(7)$, el campo con 7 elementos.

a) Encontrar un polinomio distinto de cero tal que la correspondiente función polinómica es idénticamente igual a cero.

b) Es el polinomio $6x^4+3x^3+6x^2+2x+5$ irreductible?

El trabajo hasta ahora: La primera parte es fácil. El polinomio $x^7-x$ obras de Fermat poco teorema. La segunda parte es más complicada. Si el polinomio es reducible, hechos en el producto de un término lineal y algo más, o que factores como dos cuadráticas. El primer caso es fácil excluir; simplemente conecte todos los siete elementos de la $\mathbb{Z}_7$ en el polinomio y confirmar ninguno de ellos es una raíz. La segunda es más difícil. Por supuesto, sólo pudo configurar los sistemas de ecuaciones resultantes de

$$(ax^2+bx+c)(dx^2+ex+f)$$

y de ir a través de todos los posibles valores de $a,c,d,f$ y ver si los valores resultantes de $b$ $e$ son permisibles, y aunque sé que el tiempo me da la respuesta, no tengo ningún deseo de hacer todos esos cálculos. Hay un impermeable manera?

Answer 1

Sugerencia $\ $ Como se sugirió que podría usar el método de prueba y error, y el programa de una computadora para probar la $7^4 = 2401$ de los casos que surgen de la $4$ coeficientes indeterminados en una factorización en dos cuadráticas. Pero, como suele suceder, un poco de conocimiento supera a la fuerza bruta. Por la explotación de los innata de simetría, podemos reducir el $2401$ casos $2$ de los casos. En primer lugar, desplazando $\rm\:x\to x\!-\!1\:$ a matar a la $\rm\:x^3\:$ plazo de los rendimientos de

$$\rm\begin{eqnarray} -f(x\!-\!1) &\equiv&\rm\ \ \ x^4\ +\ 2\ x^2\ -\ 3\ x\ +\ 2\pmod 7 \\ &\equiv&\rm\ (x^2\!- a\, x + b)\ (x^2\! + a\, x + c)\\ &\equiv&\rm\ \ x^4\! + (b\!+\!c\!-\!a^2)\!\: x^2\! + a(b\!-\!c)\:\!x + bc\end{eqnarray} $$

Hasta el $\rm\, b,c\, $ swaps, $\rm\: bc\equiv 2\!\iff\! (b,c)\, \equiv\, \pm(2,1),\, \pm\:\!(3,3).\:$ $\rm\:b\not\equiv c\:$ otra cosa coef de $\rm\,x\,$$\,0\not\equiv -3$.

Si $\rm\ (b,c) \equiv\ \ \: (\ 2,\ 1\ )\ $ $\rm\:-3 \equiv a(b\!-\!c)\equiv\ \: a\:\ $ $\rm\:b\!+\!c\!-\!a^2\equiv\ \ \ \, 2\!+\!1\!-\!(-3)^2\equiv\ \ 1\:\not\equiv 2$

Si $\rm\ (b,c) \equiv (-2,\!-1)\:$ $\rm\:-3 \equiv a(b\!-\!c)\equiv -a\:$ $\rm\:b\!+\!c\!-\!a^2\equiv\, -2\!-\!1\!-\!(+3)^2\equiv -5 \equiv 2$

Por lo $\rm\:a,b,c \equiv 3,-2,-1,\:$ es una solución que obtiene la factorización $$\rm -f(x\!-\!1)\, \equiv\, x^4 + 2\,x^2 - 3\,x+2\, \equiv\, (x^2-3\,x-2)(x^2+3\,x-1)\pmod 7$$

Por lo tanto, $\rm\:f(x)\:$ es reducible desde $\rm\:x\to x\!+\!1\:$ por encima de los rendimientos de la factorización de $\rm\:-f(x).\ \ $ QED

Comentario $\ $ como alternativa, puede utilizar el algoritmo de Euclides para calcular $\rm\:gcd(f(x\!+\!c),x^{24}\!-\!1)\:$ random$\rm\:c,\:$, $\,$ $\rm\:c=1\:$ rápidamente los rendimientos $\rm\:x^2\!+\!2\:|\:f(x\!+\!1),\:$ por lo tanto $\rm\:f(x)\:$ tiene el factor de $\rm\:(x\!-\!1)^2\!+\!2\, =\, x^2-2\,x+3.\:$ Esta es la forma en que algunos algoritmos de factorización de trabajo.

Answer 2

La respuesta para (a) es el uso de Pequeño teorema de Fermat para el caso primos entre sí, es decir, sabemos que $$ x ^ 7 \ equiv x \ pmod {7} $$ $$ tan x ^ 7 - x \ equiv 0 \ {pmod 7}. $$ El caso noncoprime, es decir,$x \equiv 0 \pmod{7}$ es clara.

Para la segunda respuesta, la mejor manera es en realidad la conjetura y verificación (hay algoritmos más complicados, aunque). Es un factor en $$ 6 (x ^ 2 5x 3) (x ^ 2 6x 3). $$