Teoría de números - Aritmética modular con números complejos

Question

Así que estaba viendo un problema que me pedía encontrar un$x$ st$x^3 = -1 \pmod{199}$ dado que$14^2 = -3 \pmod{199}$.

Para hacer esto, me dieron la pista para mirar números complejos, así que hice lo siguiente

ps

Entonces puedo decir eso

ps

que de hecho es una solución al problema.

Estoy buscando una explicación de por qué puedo hacer esto y cualquier información adicional sobre cómo aplicar este truco a problemas similares.

Answer 1

$x^3 + 1 = (x + 1)(x^2 - x + 1)$ y tenga en cuenta que$199$ es un Primer, por lo que

$x + 1 = 0 \ \pmod{199}$ o$x^2 - x + 1 = 0 \ \pmod{199}$.

La sugerencia$14^2 = -3 \ \pmod{199}$ para encontrar la raíz de$x^2 - x + 1$ desde:

$x^2 - x + 1 = (x - \frac{1}{2})^2 + \frac{3}{4} = 0 \ \pmod{199}$

entonces

$(2x - 1)^2 = -3 \ \pmod{199}$

---

PD

hay$3$ roots:$\{-1, 107, -106\}$

Answer 2

Déjeme que se lo explique en dos pasos de la intervención de los "números complejos" en tu problema:

1) Vamos a $p$ principal $\neq 2, 3$ $\mathbf F_p$ el valor del campo con $p$ elementos. Convenio: el recinto del hotel, todos los cálculos algebraicos tendrá lugar en una clausura algebraica $F$$\mathbf F_p$ ; para evitar confusiones, la igualdad entre dos elementos $a,b$ $F$ escrito $a\equiv b$. Debido a $p \neq 3$, la raíz cubica de $1$ $F^*$ formar un grupo cíclico de orden $3$; escribir $j$ para un generador de este grupo. Debido a $\mathbf F_p^{*}$ es cíclico de orden $p-1$, $j \in \mathbf F_p^{*}$ iff $p \equiv 1 \pmod {3}$, que es el caso de $p=199$. Entonces las soluciones de la ecuación de $x^3 + 1\equiv (x+1)(x+j)(x+j^2) \equiv 0$$\mathbf F_{199}$$1, -j, -j^2$. Sólo queda expresar $j, j^2$ $\mathbf F_{199}$ el uso de la sugerencia $14^2\equiv -3$. Para esto, observe que la habitual relación $1+j+j^2 \equiv 0$ implica $3\equiv (2+j)(2+j^2)\equiv -(1+2j)^2$, por lo que el $(1+2j)\equiv \pm 14$ y obtenemos finalmente, así como en la respuesta de @Mudream, $-j\equiv 107, -j^2\equiv-106$ (dependiendo de la elección de $j$)

2) La analogía con el complejo de 3 de raíces de la unidad, con $j=(-1 + \sqrt -3)/2$, es más que una analogía. Introducir el complejo cuadrática campo $\mathbf Q(j)$, cuyo anillo de enteros es $E:=\mathbf Z[j]$, el llamado Eisenstein anillo. Se sabe que $E $ es un UFD, por lo tanto, hasta unidades (=invertible elementos), podemos hacer operaciones aritméticas en $E$ como en $\mathbf Z$ a firmar. La irreductible (=primer) elementos de la $E$ hasta unidades son de dos tipos: (i) el aprovechamiento racional de los números primos $p\equiv -1\pmod {3}$ ; (ii) los elementos $\pi$ $E$ cuya norma (= producto de complejos conjugados) es $3$ o racional prime $p\equiv 1 \pmod{3}$ (como $199$). En este último caso, el uso de la norma, podemos resolver la congruencia $x^3 +1 \equiv 0$ $E/\pi E$ como en $\mathbf Z /p\mathbf Z$, lo que explica la "analogía" con 1) .

Answer 3

Si está trabajando en un anillo y si$s^2=-3$ tiene una solución en el anillo, entonces$x=(1+s)/2$ satisface$x^3=-1$. Las reglas de álgebra se mantienen en general en cualquier anillo con excepciones obvias tales como no poder dividir siempre por elementos que no sean cero, como$2$.

Answer 4

Dado que$\sqrt{-3}=14$, esto es fácil:

$x^3+1=0 \implies(x+1)(x^2-x+1)=0$. Entonces$x=1$, o$x^2-x+1=0$. Resolviendo el cuadrático:

$x=\dfrac{1\pm\sqrt{-3}}{2}=\dfrac{1\pm 14}{2}$

Asi que $x\in\{1,15/2,-13/2\} = \{1,107,93\}$.