Soluciones de $x^2-6x-13 \equiv 0 \pmod{127}$

Question

Comencé a aprender la teoría de los números, específicamente el polinomio de congruencias y necesita ayuda con el siguiente ejercicio. Aquí está:

¿La congruencia $x^2-6x-13 \equiv 0 \pmod{127}$ tiene soluciones?

Traté de seguir el método para la solución general de la ecuación cuadrática de la congruencia, pero no llegué muy lejos. Esto es lo que he hecho hasta ahora:

Desde $(4, 127) = 1$, podemos completar el cuadrado multiplicando por $4$ sin tener que cambiar el módulo con el fin de obtener los siguientes equivalente a la congruencia

$$(2x-6)^2 \equiv 36 - 4(-13) \pmod{127} \iff (2x-6)^2 \equiv 88 \pmod{127}.$$

Si me estoy dirigiendo en la dirección correcta, entonces no sé cómo continuar a partir de aquí. Sospecho que hay otro método para resolver este problema, ya que yo no hacer uso del hecho de que $127$ es primo. También, el problema no se requieren para encontrar las soluciones, pero sólo de determinar si existen soluciones. Posiblemente se puede evitar cálculos y hacer uso de algún teorema/lema a encontrar si la congruencia tiene soluciones o no.

Answer 1

Para encontrar soluciones de $x^2 - 6x - 13 \equiv 0 \mod 127$, debemos escribir $x^2-6x - 13$ como un cuadrado de un término lineal, además de una constante. Se ve fácilmente que $x^2 - 6x - 13 = (x-3)^2 - 22$. Por lo tanto, la congruencia es equivalente a $(x-3)^2 \equiv 22 \mod 127$.

Ahora, debemos verificar si $22$ es una ecuación cuadrática de residuos de mod $127$. Para esto, podemos utilizar el símbolo de Legendre, cuya notación voy a mantener la misma como la binomial, por lo que no se confunda. $$ \binom{22}{127} = \color{verde}{\binom{11}{127}}\color{red}{\binom{2}{127}} = \color{verde}{-\binom{127}{11}} \times \color{rojo}1 $$ donde los términos con el mismo color en la LHS y RHS son iguales. El verde de la igualdad por la reciprocidad cuadrática y la segunda viene por el hecho de que $\binom{2}{p}$ es bien conocido por los restos que $p$ deja cuando se divide por $8$.

Ahora, podemos hacer: $$ -\binom{127}{11} = -\binom{6}{11} = -\color{verde}{\binom{2}{11}}\color{red}{ \binom{3}{11}} = -\color{verde}{(-1)}\color{red}{(1)} = 1 $$

De nuevo, el color de las condiciones en el LHS y RHS son iguales debido a que las cantidades $\binom 2p$ $\binom 3p$ son bien conocidos.

Ya hemos logrado que el símbolo de Legendre es $1$, esto implica la existencia de una solución, y por lo tanto dos.

La pregunta, sin embargo, es cómo calcularlos. No sé de ningún otro método de fuerza bruta, por desgracia. Sin embargo, nuestra recompensa por escrito $(x-3)^2 \equiv 22 \mod 127$ es que nosotros, básicamente, sólo tienes que buscar plazas de la forma $127k + 22$ encontrar una solución, en lugar de tener que sustituir los valores de $x$ en la expresión de $x^2-6x-13$ cada vez.

Fuerza bruta : la serie $127k + 22 $ va de : $22,149,276,403,530,657,\color{blue}{784},...$

he aquí, $784 = 28^2$, por lo tanto esto da $x = 31$. Ahora, tenga en cuenta que la congruencia en realidad tiene dos soluciones, una dada por $127 - 28 = 99$. Se puede comprobar que $9801 = 99^2 = 22 + 127 \times 77$.

Por lo tanto, se obtienen dos soluciones de $x$, es decir,$x= 31,102$.

Answer 2

Soy una congruencia principiante como usted.

Yo lo hice de esta manera

completado el cuadrado de $(x-3)^2-9\equiv 13 \mod 127$

$(x-3)^2\equiv 22 \mod 127$

Ahora llame a $r$ es el número tal que $r^2\equiv 22\mod 127$?

Como un "modular" de la raíz cuadrada

He encontrado aquí una forma para encontrar las raíces

Como $127\equiv 3 \mod 4$, luego tenemos a $r= \pm 22^{\frac{128}{4}} \mod 127$

$22^{32} =2^{32}\cdot 11^{32}$

$2^7\equiv 1 \mod 127\to 2^{28}\equiv 1 \mod 127\to \color{red}{2^{32}\equiv 2^4\mod 127}$

$11^{32}=121^{16}$ $121\equiv 6 \mod 127$ tenemos $121^{16}\equiv 6^{16} \mod 127$ y, a continuación, $6^{16}\equiv 2^{16}\cdot 3^{16} \mod 127$

$2^k \mod 127$ $k=0,1,2\ldots$ es cíclico y es $1,2,4,8,16,32,64$ a continuación, se repite (ya $127=2^7-1$) por lo tanto, $2^{16}\equiv 4 \mod 127$

$3^{16}\equiv 81^4 \mod 127\to 3^{16}\equiv 71 \mod 127$

Finalmente, $6^{16}\equiv 4\cdot 71 \mod 127\to 6^{16}\equiv 30 \mod 127$ $\color{red}{11^{32}\equiv 6^{16}\equiv 30 \mod 127}$

La recogida de las piezas en color rojo obtenemos $22^{32}\equiv 2^4\cdot 30 \mod 127$ $22^{32}\equiv 99\mod 127$ $-22^{32} \equiv 28 \mod 127$

La conclusión de las dos soluciones se $x-3\equiv 99 \mod 127\to x\equiv 102 \mod 127$ $x-3\equiv 28 \mod 127 \to x\equiv 31 \mod 127$

Editar

Mi solución es de todos, pero elegante. De todos modos es una solución proporcionada por un novato como tú y espero que sea comprensible

Answer 3

Utilizando el Algoritmo de Berlekamp para factorizar un polinomio sobre $\mathbb{F}_{127}$ podemos obtener inmediatamente que $$ x^2-6x-13=(x+25)(x+96). $$ Así que tenemos dos soluciones.

Answer 4

Esta ecuación tiene raíces modulo $127$ si y sólo si la reducción del discriminante $\Delta'=9+13$ es un cuadrado modulo $127$. Vamos a utilizar las leyes de la reciprocidad cuadrática.

$$\biggl(\frac{22}{127}\biggr)=\biggl(\frac{2}{127}\biggr)\biggl(\frac{11}{127}\biggr)=\biggl(\frac{11}{127}\biggr)\quad\text{since }127\equiv -1\mod8\quad (2^{\mathit{nd}}\textit{supplementary law}). $$ Ahora tenemos \begin{align}\biggl(\frac{11}{127}\biggr)&=\biggl(\frac{127}{11}\biggr)\bigl(-1\bigr)^{\tfrac{10\cdot126}4}=-\biggl(\frac{6}{11}\biggr)=-\biggl(\frac{2}{11}\biggr)\biggl(\frac{3}{11}\biggr)\\[1ex] &=+\biggl(\frac{3}{11}\biggr)=\biggl(\frac{11}{3}\biggr)\bigl(-1\bigr)^{\tfrac{2\cdot10}4}=-\biggl(\frac{2}{3}\biggr)=+1. \end{align} Así, la ecuación tiene raíces.

Answer 5

Creo que se puede tratar de $$x=31.$$ es válido.

Finalmente tenemos $$x^2-6x-13\equiv(x-31)(x-102) \pmod{127}.$$