Para resolver las raíces de un polinomio en $\mathbb{Z}_p$

Question

Esta es probablemente una simple pregunta. y me gustaría trabajar en un ejemplo.

¿Cómo solucionamos $x^2 + x + [1] = 0$ en el campo $\mathbb{Z}_7$?

Trataba de un caso simple, por ejemplo: $[4] x - [3] = 0$, dónde $x = [3][4]^{-1}$ donde encontramos $[4]^{-1} = [2]$ lo $x = [6]$

Pero me confundo en el caso de la cuadrático. ¡Cualquier idea sería genial!

Answer 1

No es difícil mostrar que la fórmula cuadrática todavía funciona a través de un campo no de la característica $2$. Para la cuadrática $ax^2+bx+c$ puede ser útil pensar en las raíces dadas por la QF como $$ (2a)^{-1}\left(-b + \sqrt{b^2-4ac}\right). $$ Pero, usted tiene dos raíces cuadradas en general (un buen ejercicio!) así que usted debe aplicar esa fórmula para todas las raíces cuadradas (explicando por qué usted tiene el $\pm$ en la familiar real/complejo caso). También puede escribir en la forma familiar $$ (2a)^{-1}\left(-b \pm \sqrt{b^2-4ac}\right) $$ pero esto asume que usted ha preferido una raíz cuadrada, que rara vez tiene sentido. Pero eso es un poco nitpicky.

En tu ejemplo, tenéis necesidad de todas las raíces cuadradas de los $4 \bmod 7$, que se $2$$-2=5$. Ahora $2^{-1}=4$ y las fórmulas de dar soluciones $$ x = 4(-1+2) = 4 $$ y $$ x=4(-1+5) = 16=2. $$

Creer en la fórmula cuadrática, se puede conectar y comprobar que funciona. Desde un cuadrática sobre un campo tendrá en la mayoría de las dos raíces, esto probablemente hace.

También estoy no realmente bromeando acerca de mi "probarlo todo" comentario. Esto puede ser muy eficaz, especialmente para los polinomios de mayor grado y, especialmente, sobre campos finitos (cuanto más mejor). Una vez que empiece a raíz de la caza por la fuerza bruta, si usted encuentra que $x=r$ es una raíz, largo dividir el polinomio $f(x)$$x-r$. Usted recibirá $$ f(x) = (x-r)q(x) $$ para algunos polinomio $q(x)$ de MENOR grado. Las otras raíces de $f(x)$, si alguna, se ocultan en $q(x)$. Pero $q(x)$ es de menor grado, por lo que usted ha hecho su vida más fácil. Ahora continuar.

Answer 2

Mi forma de ver este particular polinomial, $X^2+X+1$, es esto: es el polinomio define las primitivas raíces cúbicas de la unidad en cualquier campo está considerando características $\ne3$.

Pero conozco Cuáles son las raíces primitivas de cubo de $1$ $\Bbb F_7$, son $2$ y $4$. Es decir, $\Bbb F_7$, obtenemos $(X-2)(X-4)=X^2+X+1$. Y ya está.

Answer 3

Supongamos $F$ es cualquier campo con

$\text{char}(F) \ne 2, \tag 1$

y

$q(x) = x^2 + ax + b \in F[x] \tag 2$

es una ecuación cuadrática polinomio con coeficientes en $F$; queremos encontrar los ceros de $q(x)$; corto de simplemente evaluando $q(x)$ para sucesivos elementos de la $x \in F$ (que, en cualquier caso, en principio, sólo se garantizan el éxito al $\vert F \vert < \infty$), lo que se puede hacer?

Bien, vale la pena señalar que algunos bien conocidos, de procedimientos ordinarios, tales como completar el cuadrado y su primo el de la fórmula cuadrática puede ser implementado como siempre y cuando (1) se aplica. De hecho, con

$q(x) = 0 \tag 3$

podemos escribir

$x^2 + ax = -b, \tag 4$

y, a continuación, agregue $a^2/4$ a cada lado; por (1), este es un muy bien definido por el elemento de $F$; obtenemos

$\left (x + \dfrac{a}{2} \right )^2 = a^2 + ax + \dfrac{a^2}{4} = \dfrac{a^2}{4} - b; \tag 5$

si entonces existe $c \in F$ con

$c^2 = \dfrac{a^2}{4} - b, \tag 6$

(4) se convierte en

$\left (x + \dfrac{a}{2} \right )^2 = c^2, \tag 7$

de dónde

$x + \dfrac{a}{2} = \pm c, \tag 8$

o

$x = -\dfrac{a}{2} \pm c. \tag 9$

Por lo que el problema de la búsqueda de soluciones a (3) es equivalente a la determinación de si $a^2/4 - b$ es un cuadrado perfecto en $F$; de hecho, incluso podemos escribir (9) en la forma

$x = -\dfrac{a}{2} \pm \sqrt{\dfrac{a^2}{4} - b} = \dfrac{-a \pm \sqrt{a^2 -4b}}{2}, \tag{10}$

familiar para nosotros como la famosa "fórmula cuadrática", asumiendo, por supuesto, un $c \in F$, como en (6) existe.

En el presente caso de $F = \Bbb Z_7$, la no-cero plazas son

$1 = 1^2 = 6^2, \; 2 = 3^2 = 4^2, \; 4 = 2^2 = 5^2; \tag{11}$

si

$q(x) = x^2 + x + 1, \tag{12}$

tenemos

$a = b = 1, \tag{13}$

de dónde

$c^2 = \dfrac{a^2}{4} - b = \dfrac{1}{4} - 1 = 2 - 1 = 1; \tag{14}$

así

$c = 1, 6, \tag{15}$

y

$x = -\dfrac{1}{2} \pm 1 = 3 \pm 1 = 2, 4; \tag{16}$

ambos de estos resultados se pueden comprobar fácilmente.

Por supuesto, si estamos buscando las raíces de la evaluación sistemática de $q(x)$ a los diferentes elementos de $F$, una vez que hemos descubierto uno de ellos, tal como $2$, podemos encontrar a los otros a través de la división $q(x)$$x - 2$, o (mucho menos trabajo!) recordando que $-a$ debe ser la suma de los mismos, de donde el segundo cero es$-1 - 2 = -3 = 4$$\Bbb Z_7$.

Si nos encontramos con una ecuación cuadrática para que $a^2/4 - b$ es no es un cuadrado perfecto, entonces ese $q(x)$ no se separan más de $F$, y debemos tener en cuenta la extensión del campo $F[x]/(q(x))$ a split $q(x)$; pero ese es otro capítulo en una larga, larga historia.