¿Puede alguien explicar por qué las dos soluciones de $n^2+7n-2 = 0$ modulo $43$ son $n=13$ y $n=23$ y cómo se encuentran?
Respuestas
¿Demasiados anuncios?
La congruencia equivale a $4n^2+28n-8\equiv 0\pmod{43}$ (multiplicamos por $4$ .) Esto se puede reescribir como $$(2n+7)^2-49-8\equiv 0\pmod{43}.$$
Equivalentemente, queremos resolver $(2n+7)^2\equiv 14\pmod{43}$ .
Desde $86+14=100$ Probablemente podamos detectar inmediatamente la solución $2n+7\equiv 10\pmod{43}$ y luego por simetría $2n+7\equiv -7\pmod{43}$ .
Ahora tenemos dos congruencias lineales que resolver $n$ , a saber $2n+7\equiv 10\pmod{43}$ y $2n+7\equiv -10\pmod{43}$ .
Para resolver la primera, reescribir como $2n\equiv 3\equiv 46\pmod{43}$ , dando la solución $n\equiv 23\pmod{43}$ . El otro cálculo es muy similar.
Nótese que hemos utilizado esencialmente una versión de la Fórmula Cuadrática.
Generalizaciones: El procedimiento que utilizamos es general . Dejemos que $p$ sea un primo impar, y consideremos la congruencia cuadrática $an^2+bn+c\equiv 0\pmod{p}$ , donde $p$ no divide $a$ . Reescribe la congruencia como $4a^2+4ab+4ac\equiv 0\pmod{p}$ y completar el cuadrado como en el caso anterior.
Pero nos quedamos con una congruencia de forma $x^2\equiv d\pmod{p}$ . Existen métodos computacionales sencillos para comprobar si esta congruencia tiene solución. (La mitad de las veces no la tiene, y entonces la congruencia original no tiene solución).
Para los primos de la forma $4k+3$ Hay una manera fácil de calcular las soluciones cuando existen, esencialmente utilizando el Teorema de Fermat. Para otros primos $p$ hay buenos algoritmos para resolver la congruencia $x^2\equiv d\pmod{p}$ incluso para los más grandes $p$ . Para más detalles, puede consultar el artículo de Wikipedia sobre el algoritmo Tonelli-Shanks.
Observación: Multiplicamos por $4$ para preparar la generalización. Sin embargo, en nuestro caso podemos completar el cuadrado de forma algo más sencilla, sustituyendo $7$ por $50$ . A continuación, observe que $n^2+50n-2=(n+25)^2-627$ y podemos sustituir $627$ por $25$ , haciendo que las soluciones sean obvias.
user772913
Puntos
56
Pista I Haz que el polinomio sea la suma de un cuadrado y otro número.
Pista II ¿Qué es? $7/2\pmod {43}$ ?
Echa un vistazo a esta página si aún no estás familiarizado con la aritmética modular: Aquí sólo estamos calculando cosas módulo a un primo, es decir, si la diferencia de dos números es divisible por $43$ entonces los consideramos iguales. Y esto explica lo que entendemos por la inversa de un número: si $ab$ se considera igual a $1$ en nuestro nuevo punto de vista, entonces decimos que $b$ es la inversa de $a$ y denotar por $a^{-1}$ .
¿Puedes llevarlo desde aquí?
Pedro Tamaroff
Puntos
73748
El número $43$ es un primo, por lo que podemos trabajar como lo hacemos siempre, por ejemplo, con los números reales: todas las mismas reglas se aplican a los enteros módulo $43$ . Ahora, buscamos completar el cuadrado . Todas las igualdades están en $\Bbb Z/43\Bbb Z$ los enteros módulo $43$ :
$${n^2} + 7n - 2 = 0$$
$${n^2} + 2\frac 72n - 2 = 0$$
Tenga en cuenta que $2$ tiene como inverso el número $22$ desde $2\times 22=44=1 \pmod {43}$ . Así, $\dfrac 7 2=7\times 2^{-1}=7\times 22=25$ . Entonces obtenemos
$$\begin{align}n^2+2\cdot 25 n-2+25^2-25^2&=0\\ (n+25)^2&=25^2+2\\(n+25)^2&=25\\n+25&=\begin{cases}5\\-5\end{cases}\\n&=\begin{cases}-20=23\\-30=13\end{cases}\end{align}$$
abyss.7
Puntos
130
Significan que los restos de $13^2+7\cdot13-2$ y de $23^2+7\cdot23-2$ son cero después de la división por $43$ .
Si dos números $n$ y $n+43k$ difieren en un múltiplo de $43$ entonces los restos después de la división por $43$ de $n^2+7n-2$ y $(n+43k)^2+7(n+43k)-2$ son los mismos. Para ver esto es suficiente para mostrar que su diferencia es múltiplo de $43$ . De hecho, $\left((n+43k)^2+7(n+43k)-2\right)-\left(n^2+7n-2\right)=2\cdot43nk+43^2k^2+7\cdot43k$ que es múltiplo de $43$ .
Esto significa que para encontrarlos basta con probar los restos de $n^2+7n-2$ evaluado en cada $n=0,1,\ldots,42$ , en la división por $43$ . Lo análogo es cierto en general para cualquier polinomio módulo de cualquier número $p$ . Basta con buscar los ceros entre $0,1,\ldots,p-1$ .
