Cómo resolver $x^2 \equiv 12 \pmod {13}$?
Resolver $x^2 \equiv 12 \pmod {13}$
Adivinando puedo decir que las soluciones son $5$ y $8$, pero ¿hay otra forma de encontrar la solución además de adivinar?
Respuestas
Como mencionó cosmo5 en su comentario. Puede hacer lo siguiente, que es un poco mejor que adivinar, ya que probablemente pueda reconocer instantáneamente los números cuadrados. Por cada número natural$n$ tenemos $$ x^2 \equiv 12 \mod 13 \quad\Leftrightarrow\quad x^2 \equiv 12+13n \mod 13. $$ Por lo tanto, puede comenzar $$ \begin{array}{c|c} n & 12+13n \\ \hline 1 & 25 \\ 2 & 38 \\ 3 & 51 \\ 4 & 64 \end{array} $$ Entonces lo verás por $n=1$ tienes $5^2$ y para $n=4$ tienes $8^2$, que te da las soluciones $x_1=5$ y $x_2=8$.
Alternativamente, puedes hacer una división polinomial después de encontrar una solución, porque $$ x^2-12 \equiv (x-x_1)(x-x_2) \mod 13. $$ Sin embargo, esto puede llevar más tiempo que adivinar números pequeños.
Insinuación :
Como $x^2 \equiv a^2 \pmod {n}$ es más fácil de manejar y $12\equiv25 \pmod {13}$, tenemos
$$ x^2 \equiv (\pm 5)^2 \pmod {13}$$
En el caso especial de tratar de encontrar una raíz cuadrada de $-1$ modulo a prime $p \equiv 1 \pmod{4}$, podemos usar el siguiente algoritmo: primero, seleccione un número entero aleatorio $a$ con $1 < a < p - 1$. Ahora si$p-1 = 2^k \cdot q$ con $q$ extraño, luego forma $a^q \operatorname{mod} p$. Si obtienes algo diferente a$1$ o $-1$ en este punto, luego cuadre repetidamente hasta que obtenga $-1$. Entonces, el número justo antes$-1$ será una raíz cuadrada de $-1$. (La razón por la que esto funciona: por el pequeño teorema de Fermat,$a^{p-1} \equiv 1 \pmod{p}$, así que después de tomar la plaza $k$ veces, llegas a $1$. Ya que$p$ es primo, el número justo antes de llegar $1$ por primera vez se ve obligado a ser $-1$.)
Por otro lado, si $a^q \equiv \pm 1 \pmod{p}$ ya, luego regrese y elija otro valor aleatorio de $a$intentar. Ya que$q < \frac{p - 1}{2}$, es imposible para cada valor de $a$ satisfacer $a^q \equiv \pm 1 \pmod{p} \Leftrightarrow a^{2q} \equiv 1 \pmod{p}$.
Entonces, en el caso de $p = 13$, dónde $p - 1 = 2^2 \cdot 3$ y entonces $q = 3$, comencemos primero con una prueba de $a = 2$. Luego,$a^q = 2^3 = 8$ y $8 \not\equiv \pm 1 \pmod{13}$, así que estamos listos para comenzar. De aquí,$8^2 = 64 \equiv -1 \pmod{13}$, por lo que encontramos 8 como raíz cuadrada de $-1 \pmod{13}$.
En el campo ${\displaystyle \mathbb {Z} /13\mathbb {Z}}$, $\,[1] + [1] \ne [0]$, y por lo tanto hay cero o dos distintos $\text{modulo-}13$ soluciones para,
$\tag 1 x^2 \equiv 12 \pmod{13}$
Cuando una solucion $[u]$ se ha encontrado la otra solución es $-[u]$.
Tenemos
$\; \large x^2 \equiv 12 \pmod{13} \; \text{ iff }$
$\; \large x^2 \equiv 2^{-2} \cdot (2^2 \cdot 12) \pmod{13} \; \text{ iff }$
$\; \large x^2 \equiv 2^{-2} \cdot (3^2) \pmod{13} \; \text{ iff }$
$\; \large x^2 \equiv \bigr(2^{-1} \cdot 3^1\bigr)^2 \pmod{13}$
Ahora la inversa de $[2]$ se calcula fácilmente,
$\quad [2]^{-1} = [\frac{13 + 1}{2}] = [7]$
y así una solución para $\text{(1)}$ es dado por
$\quad x \equiv 7 \cdot 3 \equiv 8 \pmod{13}$
La otra solución viene dada por
$\quad x \equiv -8 \equiv 5 \pmod{13}$
Nota: Examinar esta pregunta resultó en una conjetura ,
$\quad$ Un nuevo método para encontrar una solución (cuando existen) para $x^2 = a \pmod p$?