Introducción a congruencias cuadráticas#
Introducción#
En este capítulo vamos a dar una introducción a la congruencias cuadráticas. Primero veremos congruencias en dónde el módulo es un número primo. Mostraremos varios casos sobre ellas y cómo resolverlas. Luego veremos qué pasa con las congruencias que tienen como módulo un número compuesto. Expondremos los casos cuando un número compuesto es potencia de un solo primo y cuando es compuesto de varios primos en su factorización canónica.
Congruencias cuadráticas#
Definición 48 (Congruencia cuadrática)
Dado los enteros \(a,b,c\) y \(m\) un entero mayor que \(1\). Una congruencia cuadrática es una congruencia de la forma
Veamos algunos ejemplos de congruencias cuadráticas y como encontrar su solución.
Ejemplo 139
Consideremos la congruencia \(x^2 + 2x + 1\equiv 0\pmod{5}\).
Para encontrar una solución de esta congruencia, tendríamos que buscar los valores \(x\in \mathbb{Z}_5 = \{ 0,1,2,3,4 \}\) tales que al evaluarlos en la congruencia el resultado deje un residuo de \(0\) al dividirlo entre \(5\).
Por lo tanto, tenemos que la única solución es \(x\equiv 4\pmod{5}\).
Ejemplo 140
Ahora vamos a considerar la congruencia \(2x^2 + 3x + 2\equiv 0\pmod{5}\).
Para encontrar la solución, vamos a sustituir los valores \(x\in \mathbb{Z}_5\) tales que satisfagan la congruencia.
Como podemos observar, no hay solución ya que ningún valor satisface la congruencia.
Veamos un ejemplo en donde se pueden simplificar un poco las cuentas.
Ejemplo 141
Encuentra las soluciones de la congruencia \(x^2 - 3x + 2\equiv 0\pmod{15}.\)
Solución.
Una forma de simplificar los cálculos es completar cuadrados en la congruencia.
Si seguimos la idea anterior, tendríamos que completar cuadrados en el lado izquierdo de la congruencia y obtendríamos lo siguiente
Si hacemos \(s \equiv x + 6\pmod{15}\), entonces tendríamos que buscar los valores de \(s \in \mathbb{Z}_{15} = \{ 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14 \}\) tales que cumplan la congruencia \(s^2\equiv 4\pmod{15}\). A continuación mostramos las cuentas para encontrar dichos valores,
Por lo tanto, tendríamos que \(s \equiv 2,7,8,13\pmod{15}\). Como \(x \equiv s - 6 \pmod{15}\), obtendríamos \(4\) soluciones para \(x\):
Por lo tanto \(x \equiv 1,2,7,11\pmod{15}\). Vamos a comprobar los resultados obtenidos.
Por lo tanto, hemos encontrado las soluciones de la congruencia cuadrática.
Cuando tenemos congruencias sin el término lineal, es decir \(x^2 - a \equiv 0\pmod{m}\) podríamos resolverlo dejando el término \(x^2\) solo.
Ya hemos tenido un encuentro con este tipo de congruencias cuadráticas. En la Definición 40 vimos que un entero \(a\) es inverso de sí mismo si se cumple que \(a^2\equiv 1\pmod{m}\). Esto se podría pensar como un ejercicio de resolver una congruencia cuadrática. Veamos un ejemplo.
Ejemplo 142
Verifica si la congruencia \(x^2 - 1\equiv 0 \pmod{8}\) tiene solución.
Solución.
Si dejamos el término \(x^2\) solo, nos queda la congruencia \(x^2\equiv 1\pmod{8}\).
Para resolver la congruencia tendríamos que revisar los valores \(x \in \mathbb{Z}_8 = \{ 0,1,2,3,4,5,6,7 \}\).
No hace falta que revisemos todos los valores, ya que por el Teorema 34 sabemos que \(x\in \mathbb{Z}_8\) tiene inverso multiplicativo si y sólo si \((x,m) = 1\). Entonces basta verificar los valores \(1,3,5,7\)
Por lo tanto tenemos que \(x \equiv 1,3,5,7 \pmod{8}.\)
Ejemplo 143
Verifica si la congruencia \(x^2 - 1\equiv 0\pmod{7}\) tiene solución.
Solución.
Si dejamos el término \(x^2\) solo, nos queda la congruencia \(x^2\equiv 1\pmod{7}\).
Para resolver la congruencia tendríamos que revisar los valores \(x\in \mathbb{Z}_7 = \{ 0,1,2,3,4,5,6 \}\). Luego, obtenemos que
Por lo tanto, tenemos que \(x \equiv 1,6\pmod{7}\).
Congruencias cuadráticas en módulos primos#
Como sabemos, el único número primo par es el \(2\) y en realidad resolver congruencias con módulo \(2\) solo tendría dos posibles soluciones \(x\equiv 0\pmod{2}\) y \(x\equiv 1\pmod{2}\).
Teorema 61
Sea \(a\) un entero impar. Entonces la congruencia \(x^2\equiv a\pmod{2}\) tiene solución.
Demostración. Notemos que como \(a\) es un entero impar, entonces es de la forma \(a = 2k + 1\). Esto quiere decir que \(2k = a - 1\), en otras palabras \(2|(a-1)\) y por la Definición 35 tendríamos que \(a\equiv 1\pmod{2}\). Entonces nos quedaría la congruencia \(x^2\equiv 1\pmod{2}\) y su única solución sería \(x\equiv 1\pmod{2}\). \(\square\)
En lo que sigue vamos a trabajar con congruencias que tengan módulos primos más grandes que \(2\).
Como vimos en el Ejemplo 141, podemos utilizar el método de completar cuadrados para resolver las congruencias cuadráticas. Este método puede ser utilizado para congruencias que tienen la forma \(ax^2 + bx + c\equiv 0\pmod{p}\), en donde el módulo es un número primo.
Vamos a aplicar una serie de pasos a la congruencia \(ax^2 + bx + c\equiv 0\pmod{p}\) para desarrollar una fórmula que nos ayude a completar cuadrados de manera sencilla. Supongamos que \(p\) es un primo impar y que \(p\nmid a\) para evitar que la congruencia se convierta en una congruencia lineal. Además como \(p\nmid a\) entonces \(p\nmid 4a\). Así, tendríamos lo siguiente
Ahora, si hacemos \(s = 2ax + b\) y \(r = b^2 - 4ac\), tenemos la congruencia \(s^2\equiv r\pmod{p}\). Entonces si encontramos el valor de \(s\) que cumple la congruencia, podríamos encontrar el valor de \(x\) despejándose de la ecuación \(s = 2ax + b\). Con esto logramos reducir los cálculos para la búsqueda de la solución.
Notemos lo siguiente, como \(p\nmid a\), entonces tenemos que \((a,p) = 1\), como \(p\) es un primo impar también se cumple que \((4a,p) = 1\) y por lo tanto \(4a\) tendría inverso multiplicativo.
La condición de que \(4a\) tenga inverso multiplicativo módulo \(p\), nos sirve para que podamos revertir todos los pasos y que la solución encontrada satisfaga la congruencia original.
Observación 19
Con lo anterior, podemos notar que la congruencia \(ax^2 + bx + c \equiv 0 \pmod{p}\) tiene solución si y sólo si la congruencia \(s^2\equiv r\pmod{p}\) tiene solución, donde \(s = 2ax + b\) y \(r = b^2 - 4ac\).
Observación 20
Notemos que si \(p|r\), entonces la congruencia se simplifica a \(s^2\equiv 0\pmod{p}\), por lo cual \(s \equiv 0\pmod{p}\) sería la única solución.
El siguiente lema nos dará una idea de como son las soluciones de las congruencias \(x^2\equiv a\pmod{p}\).
Lema 14
Sea \(p\) un primo impar y \(a\) un entero tal que \(p\nmid a\). Entonces la congruencia \(x^2\equiv a\pmod{p}\) puede no tener soluciones o tener \(2\) soluciones incongruentes.
Demostración. Veremos que si \(\alpha\) es solución, entonces \(-\alpha\) es solución.
Si \(\alpha\) es una solución, entonces satisface la congruencia, \(\alpha^2 \equiv a\pmod{p}\). Sea \(\beta = p-\alpha\). Entonces tendríamos que
Ahora veamos que ambas soluciones son incongruentes. Procedamos por contradicción es decir que \(\beta \equiv \alpha \pmod{p}\), entonces tendríamos que
Luego como \((2,p) = 1\), \(2\) tiene inverso multiplicativo y si multiplicamos este inverso en ambos de la congruencia obtendríamos que \(\alpha \equiv 0\pmod{p}\), lo cual es una contradicción.
Así, \(\alpha\) y \(p - \alpha\) son dos soluciones incongruentes.
Para ver que tiene exactamente dos soluciones, supongamos que existe una tercera solución \(\gamma\).
Entonces tendríamos que \(\gamma^2 \equiv \alpha^2 \pmod{p}\), luego por la Definición 35 se cumple que \(p|(\gamma^2 - \alpha^2) = (\gamma - \alpha)(\gamma + \alpha)\), es decir que \(p|(\gamma - \alpha)\) o \(p|(\gamma + \alpha)\), estos significa que \(\gamma \equiv \alpha \pmod{p}\) o \(\gamma \equiv -\alpha \equiv \beta \pmod{p}\). Por lo tanto hemos demostrado que la congruencia no puede tener mas de dos soluciones. \(\square\)
Observación 21
Notemos que el Lema 14 nos dota de una forma de encontrar la segunda solución de la congruencia \(x^2\equiv a\pmod{p}\). Si encontramos una solución \(\alpha\), entonces la segunda solución esta dada por su inverso aditivo \(-\alpha\).
En el Ejemplo 143, resolvimos la congruencia \(x^2\equiv 1\pmod{7}\) y encontramos las soluciones \(x \equiv 1,6\pmod{7}\). Pero podemos observar que \(6\equiv -1\pmod{7}\), entonces las soluciones las podemos expresar como \(x\equiv \pm 1\pmod{7}\).
El Lema 14 también nos ayuda a reducir la búsqueda de las soluciones. Como vimos, si resolvemos una congruencia módulo \(p\) entonces esta tiene dos soluciones: una es \(\alpha\) y la segunda sería \(-\alpha\). Estas soluciones las encontramos dentro del conjunto \(\mathbb{Z}_p\), pero gracias al lema sólo tenemos que buscar una solución entre el rango de valores de \(1\) a \(\frac{p-1}{2}\) y la segunda solución la encontraremos con el inverso aditivo.
Ejemplo 144
Resuelve la congruencia \(2x^2 + x + 1 \equiv 0\pmod{11}\).
Solución.
Usando la fórmula que construimos para completar cuadrados, la congruencia sería equivalente a \((2ax + b)^2 \equiv b^2 - 4ac \pmod{p}\) y sólo tenemos que sustituir los valores y simplificar las cuentas.
Entonces hacemos \(s = 4x + 1\) y ahora tendríamos que resolver la congruencia \(s^2\equiv 4\pmod{11}\).
Buscaremos una solución dentro del rango \(1\) a \(5\),
Una solución es \(s\equiv 2\pmod{11}\), la otra solución es \(s\equiv -2\equiv 9\pmod{11}\). Si verificamos, obtenemos que \(9^2 = 81\equiv 4\pmod{11}\).
Por lo tanto, \(s\equiv \pm 2\pmod{11}\).
Ahora necesitamos encontrar los valores para \(x\), entonces si \(s = 2\),
Ahora, si \(s = -2\), tenemos que
Por lo tanto, tenemos que las soluciones de la congruencia \(2x^2 + x + 1 \equiv 0\pmod{11}\) son \(x\equiv 2,3\pmod{11}\).
Veamos un último ejemplo en el que la congruencia cuadrática no tiene solución.
Ejemplo 145
Resuelve, si es posible, la congruencia \(3x^2 + 7x + 5\equiv 0\pmod{13}\).
Solución.
Primero vamos a completar cuadrados.
Si hacemos \(s = 6x + 7\), entonces tendríamos que buscar un valor \(s\in \{1,2,3,4,5,6 \}\) tal que satisface la congruencia \(s^2\equiv 2\pmod{13}\). Hagamos los casos:
Como podemos observar, la congruencia \(s^2\equiv 2\pmod{13}\) no tiene solución y por lo tanto no hay solución para la congruencia \(3x^2 + 7x + 5\equiv 0\pmod{13}\).
Pasemos a ver otro método para resolver congruencias cuadráticas de la forma \(ax^2 + bx + c\equiv 0\pmod{p}\). Supongamos que podemos factorizar el lado izquierdo de la congruencia, es decir, que podemos obtener una expresión del tipo
Luego por la Definición 35 tendríamos que
Entonces podríamos plantear las congruencias
Luego, si resolvemos estas congruencias lineales obtendríamos las dos soluciones de la congruencia cuadrática.
Ejemplo 146
Resuelve la congruencia \(13x^2 -2x - 15\equiv 0\pmod{17}\).
Solución.
Notemos que podemos factorizar el lado izquierdo, \(13x^2 -2x - 15 = (13x - 15)(x + 1)\). Entonces tendríamos la congruencia
La segunda congruencia está casi resuelta, pues tendríamos que
Por lo tanto tenemos que las soluciones son \(x\equiv 9,16\pmod{17}\).
Veamos algunos ejemplos interesantes sobre congruencias cuadráticas.
Ejemplo 147
Verifica que las congruencias \(x^2\equiv 7\pmod{13}\) y \(x^2\equiv 5\pmod{13}\) no tienen solución, pero \(x^2\equiv 35\pmod{13}\) sí tiene solución.
Solución.
Vamos a ver qué pasa con los elementos del conjunto \(\mathbb{Z}_{13}\) cuando los elevamos al cuadrado.
Con los resultados anteriores, podemos notar que las congruencias \(x^2\equiv 7\pmod{13}\), \(x^2\equiv 5\pmod{13}\) no tendrían solución.
Pero la congruencia \(x^2\equiv 35\equiv 9\pmod{13}\) sí tiene soluciones, las cuales son \(x\equiv 3,10\pmod{13}\).
Aún nos faltan herramientas para demostrar el siguiente enunciado, pero vamos a ver un ejemplo que se cumple.
Ejemplo 148
Tomemos dos números primos diferentes \(p\) y \(q\). Si \(p = 4k+1\) o \(q = 4k+1\) entonces la congruencia \(x^2\equiv p\pmod{q}\) tiene solución si y sólo si la congruencia \(x^2\equiv q\pmod{p}\) la tiene.
Tomemos \(p = 11\) y \(q = 37 = 4\cdot 9 + 1\) lo cual cumple con que \(q\) es de la forma \(4k + 1\).
Comprobemos si la congruencia \(x^2\equiv 11\pmod{37}\) tiene solución.
Por lo tanto las soluciones son \(x\equiv \pm 14\pmod{37}\).
Entonces la congruencia \(x^2\equiv 37\equiv 4\pmod{11}\) debería tener solución. Y en efecto, notemos que
Donde las soluciones son \(x\equiv \pm 2\pmod{11}\).
Código para resolver una congruencia cuadrática#
Vamos a contruir un código que nos ayude a resolver congruencias de la forma \(ax^2 + bx + c\equiv 0\pmod{p}\), en donde \(p\) es un número primo.
Vamos a ocupar la función que creamos para calcular el inverso de un entero módulo \(m\).
def euclides_extendido_ciclos(a,b):
s=[1,0]
t=[0,1]
while b!=0:
q=a//b
r=a%b
nuevo_s=s[-2]-q*s[-1]
nuevo_t=t[-2]-q*t[-1]
s.append(nuevo_s)
t.append(nuevo_t)
a,b=b,r
return s[-2],t[-2],a
def inverso_modn(a,m):
alfa,beta,d = euclides_extendido_ciclos(a,m)
if d == 1:
return alfa
El siguiente código nos ayuda a resolver congruencias cuadráticas de la forma \(ax^2 + bx + c\equiv 0\pmod{p}\). La función recibe como argumentos una lista con los coeficientes de \(a\), \(b\) y \(c\).
def congr_cuadratica(list_coef, p):
if list_coef[1] == 0:
r = (-list_coef[2] * inverso_modn(list_coef[0],p))%p
for i in range(1,(p-1)//2 + 1):
if (i**2)%p == r:
return print(f"La soluciones son {i},{-i}")
print("La congruencia no tiene solución")
elif list_coef[2] == 0:
r = (-list_coef[1] * inverso_modn(list_coef[0],p))%p
return print(f"La congruencia se puede factorizar, las soluciones son 0 y {r}")
else:
r = (list_coef[1]**2 - 4*list_coef[0]*list_coef[2])%p
if r == 0:
s = 0
x_1 = ((-list_coef[1] + s) * inverso_modn((2*list_coef[0])%p,p))%p
return print(f"La única solución es {x_1}")
else:
for s in range(1,p):
if (s**2)%p == r:
s_1 = s
s_2 = (-s_1)%p
break
else:
return print("La congruencia no tiene solución")
x_1 = ((-list_coef[1] + s_1) * inverso_modn((2*list_coef[0])%p,p))%p
x_2 = ((-list_coef[1] + s_2) * inverso_modn((2*list_coef[0])%p,p))%p
return print(f"Las soluciones son {x_1}, {x_2}")
coeficientes = [7,0,-6]
congr_cuadratica(coeficientes,13)
La soluciones son 5,-5
coeficientes = [1,3,0]
congr_cuadratica(coeficientes,7)
La congruencia se puede factorizar, las soluciones son 0 y 4
coeficientes = [1,2,1]
congr_cuadratica(coeficientes,5)
La única solución es 4
coeficientes = [2,3,1]
congr_cuadratica(coeficientes,7)
Las soluciones son 3, 6
coeficientes = [3,7,5]
congr_cuadratica(coeficientes,13)
La congruencia no tiene solución
Congruencias cuadráticas en módulos compuestos#
Vamos a presentar un teorema que nos ayudará a resolver congruencias del tipo \(x^2\equiv a \pmod{p^n}\), en donde el módulo es un primo impar.
Teorema 62
Sea \(p\) un primo impar, \(a\) cualquier entero tal que \(p\nmid a\) y \(n\) un entero positivo. Si la congruencia \(x^2\equiv a\pmod{p}\) tiene solución entonces la congruencia \(x^2\equiv a\pmod{p^n}\) también tiene solución.
Demostración. Procederemos por inducción.
Base inductiva. Cuando \(n = 1\) tendríamos que \(x^2\equiv a\pmod{p}\) tiene solución.
Hipótesis inductiva. Supongamos que es cierto que la congruencia \(x^2\equiv a\pmod{p^k}\) tiene solución para un entero arbitrario \(k\ge 1\).
Paso inductivo. Ahora, probaremos que la congruencia \(x^2\equiv a\pmod{p^{k+1}}\) tiene solución. Para ello vamos a construir la solución.
Por hipótesis de inducción, tenemos que existe una solución \(\alpha\) de la congruencia \(x^2\equiv a\pmod{p^k}\), por lo cual se satisface que \(\alpha^2\equiv a\pmod{p^k}\). Por Definición 35, se tiene que \(p^k|(\alpha^2 - a)\), es decir que \(ip^k = \alpha^2 - a\), con lo cual tenemos que \(\alpha^2 = a + ip^k\) para algún entero \(i\).
Vamos a generar una solución de la forma \(\alpha + jp^k\) para la congruencia \(x^2\equiv a\pmod{p^{k+1}}\). Entonces tendríamos que
Para que se cumpla la congruencia, tendríamos que elegir \(j\) tal que \(i + 2\alpha j\equiv 0\pmod{p}\). Lo anterior es una congruencia lineal en la cual debemos encontrar el valor de \(j\). Sabemos por el Teorema 43 que esta solución existe y es única módulo \(p\), ya que \((2\alpha, p) = 1\). Con ese valor de \(j\) entonces tendríamos que la expresión \(i + 2\alpha j\) es divisible por \(p\) y así tendríamos que \((i + 2\alpha j)p^k\equiv 0 \pmod{p^{k+1}}\). Por lo tanto \((\alpha + jp^k)^2\equiv a\pmod{p^{k+1}}\) y así \(\alpha + jp^k\) es una solución de la congruencia \(x^2\equiv a\pmod{p^{k+1}}\).
Por lo tanto, hemos demostrado que si la congruencia \(x^2\equiv a \pmod{p}\) tiene solución, entonces la congruencia \(x^2\equiv a\pmod{p^n}\) es soluble para todo entero positivo \(n\). \(\square\)
El teorema anterior nos da un algoritmo para construir una solución de las congruencias de la forma \(x^2\equiv a\pmod{p^n}\) siempre y cuando la congruencia \(x^2\equiv a\pmod{p}\) tenga solución. Podríamos pensar en este teorema como una forma de comprobar si este tipo de congruencias tienen solución.
Ejemplo 149
Resuelve la congruencia \(x^2\equiv 5\pmod{11^3}\).
Solución.
Enumeraremos los pasos a seguir en el siguiente algoritmo.
Necesitamos verificar si la congruencia \(x^2\equiv 5\pmod{11}\) tiene solución. Esto lo haremos buscando el valor \(x \in \mathbb{Z}_{11}\).
Entonces tenemos que \(x\equiv 4,-4 \equiv 4,7\pmod{11}\).
Tenemos valores iniciales, \(a = 5\), \(p=11\), \(\alpha = 4\), ya que es la solución de la congruencia anterior y \(k = 1\) que es el exponente del módulo.
Vamos a expresar el valor de \(\alpha^2\) en la forma \(a + ip\) y resolveremos para \(i\), entonces tendríamos que,
Vamos a resolver la congruencia lineal \(i + 2\alpha j\equiv 0\pmod{11}\) para encontrar el valor de \(j\). Entonces tendríamos que
Por lo tanto vamos a elegir \(j = 4\).
Ahora obtenemos una solución de la congruencia \(x^2\equiv 5\pmod{11^2}\).
Para ello, la calculamos como sigue \(\alpha + jp = 4 + 4\cdot 11 = 4 + 44 = 48\). Entonces se cumple que \(48^2 \equiv 5\pmod{11^2}\).Ahora actualizamos los valores de \(\alpha\) y \(k\), haciendo \(\alpha = 48\) y \(k = 2\). Y repetiremos los pasos del \(3\) al \(5\) para encontrar una solución de la congruencia \(x^2\equiv 5\pmod{11^3}\).
Ahora expresamos el valor de \(\alpha^2\) en la forma de \(a + ip^2\) y resolvemos para \(i\). Entonces tendríamos que
Ahora resolvemos la congruencia lineal \(i+2aj\equiv 0\pmod{p}\) para encontrar el valor de \(j\).
Por lo tanto vamos a elegir \(j = 10\).
Por último, generamos una solución para la congruencia \(x^2\equiv a\pmod{p^3}\).
Para ello, la calculamos como sigue: \(\alpha + jp^2 = 48 + 10\cdot 11^2 = 48 + 1210 = 1258\).
Entonces se cumple que \(1258^2 \equiv 5\pmod{11^3}\).
Por lo tanto, tenemos que la solución de la congruencia \(x^2\equiv 5\pmod{11^3}\) es \(x\equiv 1258\pmod{11^3}\) y también \(x\equiv -1258\equiv 73\pmod{11^3}\).
Ahora vamos a presentar dos teoremas en donde el módulo es un número compuesto que tiene la forma de \(2^n\). Estos teoremas nos ayudarán a resolver congruencias del tipo \(x^2\equiv a \pmod{2^n}\).
Teorema 63
Sea \(a\) un entero impar, la congruencia \(x^2\equiv a\pmod{4}\) tiene solución si y sólo si \(a\equiv 1\pmod{4}\).
Demostración. Vamos a ver las dos implicaciones.
Primero supongamos que \(x^2\equiv a\pmod{4}\) tiene solución.
Como \(a\) es un número impar, entonces \(x^2\) también es impar. Luego, para que la multiplicación de dos enteros sea impar ambos números deben de ser impares. De lo anterior tenemos que \(x\) debe de ser impar. Sea \(x = 2k + 1\) para algún entero \(k\). Tendríamos que
Luego como \(x^2\equiv a\pmod{4}\) y \(x^2\equiv 1\pmod{4}\), entonces \(a\equiv 1\pmod{4}\).
Ahora supongamos que \(a\equiv 1\pmod{4}\).
Como \(a\equiv 1\pmod{4}\) y \(x^2\equiv a\pmod{4}\) entonces \(x^2\equiv 1\pmod{4}\), y podemos resolver esta congruencia
Teorema 64
Sea \(a\) un entero impar y \(n\) cualquier entero mayor o igual que \(3\). La congruencia \(x^2\equiv a\pmod{2^n}\) tiene solución si y sólo si \(a\equiv 1\pmod{8}\).
Demostración. Vamos a probar las dos implicaciones.
Primero supongamos que la congruencia \(x^2\equiv a\pmod{2^n}\) tiene solución.
Como la congruencia tiene solución, existe \(x = \alpha\) tal que \(\alpha^2\equiv a\pmod{2^n}\). Como se cumple para todo \(n \ge 3\), entonces tenemos que
Notemos que como \(a\) es un número impar entonces \(\alpha^2\) también es un número impar. Para que el cuadrado de un número sea impar, es porque el número en cuestión es impar,entonces \(\alpha\) debe de ser impar.
Vamos a probar que si \(\alpha\) es un número impar, entonces su cuadrado es congruente con \(1\) módulo \(8\).
Sea \(\alpha\) un número impar, entonces tiene la forma \(2k + 1\). Veamos que
Notemos que si \(k\) es par, entonces \(k+1\) es impar y si \(k\) es impar entonces \(k+1\) es par. En cualquiera de los casos \(k(k+1)\) es par. Con lo anterior tendríamos que la expresión \(4k(k+1)\) es divisible entre \(8\). Por lo tanto
Por lo tanto, \(a\equiv 1\pmod{8}\).
Ahora supongamos que \(a\equiv 1\pmod{8}\).
Probaremos por inducción que \(x^2\equiv a\pmod{2^n}\) tiene solución para toda \(n \ge 3\).
Base inductiva. Cuando \(n = 3\), tendríamos que \(x^2\equiv a\pmod{8}\) y por hipótesis \(a\equiv 1\pmod{8}\). Por lo tanto \(x^2\equiv 1\pmod{8}\). Ya vimos en el Ejemplo 142 que esta congruencia tiene soluciones las cuales son \(x\equiv 1,3,5,7\pmod{8}\).
Hipótesis inductiva. Supongamos que es verdadera la implicación, es decir que se cumple que \(x^2\equiv a\pmod{2^k}\) tiene solución para cierto valor de \(k\ge 3\).
Paso inductivo. Por la hipótesis de inducción, la congruencia \(x^2\equiv a\pmod{2^k}\) tiene una solución, digamos \(\alpha\). Como \(\alpha\) es solución entonces tendríamos que \(\alpha^2\equiv a\pmod{2^k}\). Por la Definición 35 tendríamos que \(2^k|(\alpha^2 - a)\), lo cual quiere decir que \(\alpha^2 = a + i2^k\) para algún entero \(i\). Ahora vamos a generar una solución de la forma \(\alpha + j2^{k-1}\) para la congruencia \(x^2\equiv a\pmod{2^{k+1}}\). Entonces tendríamos que
Ahora debemos elegir \(j\) tal que \(i + \alpha j\equiv 0 \pmod{2}\). Como \(\alpha\) es impar, tendríamos que \((\alpha, 2) = 1\) y por el Teorema 43 sabemos que la solución de la congruencia lineal existe y es única, es decir que podemos encontrar solución para \(j\). Con lo anterior, tenemos que \(i + \alpha j\) es divisible entre \(2\) y por lo tanto la expresión \((i + \alpha j)2^k \equiv 0\pmod{2^{k+1}}\). Por lo tanto tenemos que \((\alpha + j2^{k-1})^2 \equiv a\pmod{2^{k+1}}\).
Como consecuencia, la congruencia \(x^2\equiv a\pmod{2^{k+1}}\) tiene solución y es \(\alpha + j2^{k-1}\).
Por lo tanto hemos probado por inducción que la congruencia \(x^2\equiv a\pmod{2^n}\) tiene solución para todo entero \(n\ge 3\). \(\square\)
El Teorema 64 nos sirve para comprobar si las congruencias del tipo \(x^2\equiv a\pmod{2^n}\) tienen solución. También nos da un algoritmo para encontrar una solución y algo extra que tenemos es que si \(\alpha\) es una solución, entonces \(2^n -\alpha\) y \(2^{n-1} \pm \alpha\) son también soluciones.
Ejemplo 150
Resuelve la congruencia \(x^2 \equiv 33\pmod{64}\).
Solución.
Primero notemos que \(64 = 2^6\), y que \(33\equiv 1\pmod{8}\), por lo tanto la congruencia tiene solución.
Busquemos las soluciones de la congruencia \(x^2\equiv 33\pmod{2^3}\).
Como \(33\equiv 1\pmod{8}\), entonces \(x^2\equiv 1\pmod{8}\) y por lo tanto \(\alpha = 1\) es una solución. Luego tendríamos que \(a = 33\), entonces podemos encontrar el valor de \(i\) en la siguiente ecuación
Vamos a encontrar una solución de \(x^2\equiv 33\pmod{2^4}\), con \(k = 3\).
Tenemos que encontrar el valor de \(j\) tal que
Así, podemos elegir \(j = 0\), entonces la solución sería
Actualizamos los valores de \(\alpha, k\) y \(i\).
Ya que \(1^2\equiv 33\pmod{16}\), entonces \(\alpha = 1\) y \(k = 4\). Necesitamos calcular el valor de \(i\)
Ahora vamos a encontrar una solución para la congruencia \(x^2\equiv 25\pmod{2^5}\), con \(k = 4\).
Tenemos que encontrar el valor de \(j\) tal que
Así, podemos elegir \(j = 0\), entonces la solución sería
Actualizamos los valores de \(\alpha, k\) y \(i\).
Ya que \(1^2\equiv 33\pmod{32}\), entonces \(\alpha = 1\) y \(k = 5\), luego necesitamos calcular el valor de \(i\)
Ahora vamos a encontrar una solución para la congruencia \(x^2\equiv 25\pmod{2^6}\), con \(k = 5\).
Ahora tenemos que encontrar el valor de \(j\) tal que
Así podemos elegir \(j = 1\), entonces la solución sería
Por último buscamos las demás soluciones que son de la forma \(2^n -\alpha\) y \(2^{n-1} \pm \alpha\).
Como \(\alpha = 17\), entonces
Ahora vamos a ver cómo resolver congruencias del tipo \(x^2\equiv a\pmod{n}\), en donde \(n = pq\) y \(p\) y \(q\) son dos primos distintos. Usando el Teorema 50 podemos resolver este tipo de congruencias.
Veamos, que si tenemos la congruencia \(x^2\equiv a\pmod{p}\), como \((a,p) = 1\), entonces la congruencia tendría dos soluciones incongruentes módulo \(p\) las cuales serían \(x\equiv x_1\pmod{p}\) y \(x\equiv p-x_1\pmod{p}\). Por otro lado, la congruencia \(x^2\equiv a\pmod{q}\), también tendría dos soluciones incongruentes módulo \(q\) ya que \((a,q) = 1\), las cuales serían \(x\equiv x_2\pmod{q}\) y \(x\equiv q-x_2\pmod{q}\). Luego, podemos formar \(4\) sistemas de congruencias,
Entonces si resolvemos cada uno de los sistemas, encontraríamos \(4\) soluciones que son incongruentes módulo \(pq\).
Veamos un ejemplo para aclarar el método anterior mostrado.
Ejemplo 151
Encuentra las soluciones de la congruencia \(x^2\equiv 58\pmod{77}\).
Solución.
Notemos que \(77 = 7\cdot 11\), entonces tenemos que encontrar las soluciones de las congruencias \(x^2\equiv 58\pmod{7}\) y \(x^2\equiv 58\pmod{11}\).
Primero encontremos las soluciones de \(x^2\equiv 58\equiv 2\pmod{7}\).
Por lo tanto \(x_1\equiv 3\pmod{7}\) y la otra solución es \(p-x_1\equiv 4\pmod{7}\).
Ahora encontremos las soluciones de \(x^2\equiv 58\equiv 3\pmod{11}\).
Por lo tanto \(x_2\equiv 5\pmod{11}\) y la otra solución es \(q-x_2\equiv 6\pmod{11}\).
Entonces tenemos los siguientes sistemas de congruencias:
Vamos a resolver el sistema \(1)\). Los otros sistemas se dejan como ejercicio ya que son análogos.
\[\begin{split}1)\begin{cases} x \equiv 3\pmod{7}, \\ & \\ x \equiv 5\pmod{11}.\end{cases}\end{split}\]
Sea \(M = 7\cdot 11\), tendríamos que \(m_1 = 7\) y \(m_2 = 11\), entonces
Calculamos los inversos \(y_i\).
Ahora calculamos la solución,
Resolviendo de la misma forma los sistemas \(2,3\) y \(4\), tendríamos que \(x\equiv 17,38,39,60\pmod{77}.\)
Ya vimos un ejemplo en donde \(n\) tiene dos primos diferentes en su factorización. Es evidente que mientras \(n\) tenga más primos diferentes en su descomposición canónica, tendremos que resolver más sistemas de congruencias, y más grandes.
Explicación del código#
En este capítulo creamos un código para resolver congruencias cuadráticas de la forma \(ax^2 + bx + c\equiv 0\pmod{p}\), en donde \(p\) es un número primo. Vamos a explicar cómo funciona el código.
def congr_cuadratica(list_coef, p):
if list_coef[1] == 0:
r = (-list_coef[2] * inverso_modn(list_coef[0],p))%p
for i in range(1,(p-1)//2 + 1):
if (i**2)%p == r:
return print(f"La soluciones son {i},{-i}")
print("La congruencia no tiene solución")
elif list_coef[2] == 0:
r = (-list_coef[1] * inverso_modn(list_coef[0],p))%p
return print(f"La congruencia se puede factorizar y las soluciones son 0 y {r}")
else:
r = (list_coef[1]**2 - 4*list_coef[0]*list_coef[2])%p
if r == 0:
s = 0
x_1 = ((-list_coef[1] + s) * inverso_modn((2*list_coef[0])%p,p))%p
return print(f"La única solución es {x_1}")
else:
for s in range(1,p):
if (s**2)%p == r:
s_1 = s
s_2 = (-s_1)%p
break
else:
return print("La congruencia no tiene solución")
x_1 = ((-list_coef[1] + s_1) * inverso_modn((2*list_coef[0])%p,p))%p
x_2 = ((-list_coef[1] + s_2) * inverso_modn((2*list_coef[0])%p,p))%p
return print(f"Las soluciones son {x_1}, {x_2}")
Definimos una función llamada «congr_cuadratica» la cual recibe dos argumentos: una lista con los coeficientes de la congruencia \(ax^2 + bx + c\equiv 0\pmod{p}\), es decir «list_coef = [a,b,c]» y un entero «p» el cual debe ser un número primo.
def congr_cuadratica(list_coef, p):
Dependiendo de los coeficientes de la congruencia que se ingresen, aplicaremos un método de solución específico. Es por eso que dividimos el código en \(3\) casos, es decir, tendremos un condicional
ifseguido de unelify finalmente unelse.
En el primer caso le pedimos al código resolver congruencias en donde el valor de \(b = 0\), es decir \(ax^2 + c\equiv 0\pmod{p}\). Creamos un condicionalifen donde se verifica si el valor del segundo elemento de la lista «list_coef» es cero, de ser cierto el código dentro del condicional se reproduce.
Creamos una variable «r» en donde se calcula el valor de la incognita \(x\), de la siguiente manera
Una vez que obtenemos «r», empezamos un ciclo for con el cual recorremos los valores dentro del rango de \(1\) a \(\frac{p-1}{2} + 1\), ya que por la Observación 21 no hace falta recorrer todos los valores para encontrar la solución.
Dentro del ciclo for ponemos un condicional if en donde se verifica si el valor \(i\) que corre en el ciclo for cumple con la congruencia \(i^2\equiv r\pmod{p}\). Si esta condición se cumple, el código nos imprime en la consola que las soluciones de la congruencia son \(i\) y \(-i\).
Si la condición dentro del if no se llega a cumplir entonces el código nos imprime que la congruencia no tiene solución.
if list_coef[1] == 0:
r = (-list_coef[2] * inverso_modn(list_coef[0],p))%p
for i in range(1,(p-1)//2 + 1):
if (i**2)%p == r:
return print(f"La soluciones son {i},{-i}")
print("La congruencia no tiene solución")
El segundo caso que resolvemos es cuando el valor de \(c=0\), es decir que tendríamos la congruencia \(ax^2 + bx\equiv 0\pmod{p}\), la cual se resuelve por factorización. Como estamos trabajando en casos, ahora creamos un condicional
elifel cual tiene como condición revisar que el tercer elemento de la lista «list_coef» sea igual a cero.
Si la condición se cumple entonces se ejecuta el código dentro del condicional.
Como la congruencia se puede factorizar \(x(ax + b)\equiv 0\pmod{p}\), entonces una solución ya es cero y la otra se obtiene resolviendo la congruencia lineal \(ax + b\equiv 0\pmod{p}\). Entonces se crea una variable «r» en la cual se calcula el valor \(x\) de la congruencia lineal \(ax + b\equiv 0\pmod{p}\), de la siguiente manera
Después de encontrar la solución, el código nos imprime en la consola que la congruencia se puede factorizar y las soluciones obtenidas.
elif list_coef[2] == 0:
r = (-list_coef[1] * inverso_modn(list_coef[0],p))%p
return print(f"La congruencia se puede factorizar y las soluciones son 0 y {r}")
Por último resolvemos el caso cuando ninguno de los coeficientes de la congruencia son cero.
Como es nuestro último caso, entramos en el condicionalelse.
En este caso resolvemos la congruencia por el método de completar cuadrados, es decir que ocupamos la fórmula para completar cuadrados que desarrollamos, \((2ax + b)^2\equiv b^2 - 4ac\pmod{p}\).
Creamos la variable «r» en la cual se calcula el valor de \(b^2 - 4ac\).
Empezamos un condicionalifen el cual verificamos si el valor de «r» es igual a cero, ya que si eso sucede tendríamos la congruencia \(s^2\equiv 0\pmod{p}\), la cual su única solución es cero. Por eso creamos la variable «s» con un valor inicial de cero.
Una vez obtenido el valor de «s», podemos obtener la solución en la variable «x_1», la cual se calcula de la siguiente manera
Una vez calculada la variable «x_1» el código nos imprime que la única solución es esa.
else:
r = (list_coef[1]**2 - 4*list_coef[0]*list_coef[2])%p
if r == 0:
s = 0
x_1 = ((-list_coef[1] + s) * inverso_modn((2*list_coef[0])%p,p))%p
return print(f"La única solución es {x_1}")
Por último, si el valor de la variable «r» es diferente de cero, el código pasa al condicional
else. Dentro del condicional comienza un cicloforque recorre los valores desde \(1\) hasta \(p\). Con un condicionalifrevisamos si para el valor «s» que se recorre en el cicloforse cumple la congruencia \(s^2\equiv r\pmod{p}\).
Una vez encontrada la solución, se guarda en la variable «s_1» y se calcula la segunda solución en la variable «s_2» que es igual al inverso aditivo de «s_1».
Utilizamos la sentenciabreakpara terminar con el cicloforuna vez encontradas las soluciones.
Si en el cicloforno se encuentran soluciones, entonces el código nos imprime en la consola que la congruencia no tiene soluciones. De lo contrario, pasa a calcular las soluciones en las variables «x_1» y «x_2».
Estas soluciones también se calculan con la congruencia \(2ax + b \equiv s\pmod{p}\). Con «s_1» se calcula «x_1» y con «s_2» se calcula «x_2».
Finalmente el código nos imprime las soluciones en la consola.
else:
for s in range(1,p):
if (s**2)%p == r:
s_1 = s
s_2 = (-s_1)%p
break
else:
return print("La congruencia no tiene solución")
x_1 = ((-list_coef[1] + s_1) * inverso_modn((2*list_coef[0])%p,p))%p
x_2 = ((-list_coef[1] + s_2) * inverso_modn((2*list_coef[0])%p,p))%p
return print(f"Las soluciones son {x_1}, {x_2}")
Ejercicios de práctica#
¿Para que valores de \(a\) la congruencia \(x^2\equiv a\pmod{17}\) tiene solución.?
Encuentra las soluciones de las siguientes congruencias.
\(4x^2 + 4x - 3 \equiv 0\pmod{5}\).
\(25x^2 + 70x + 37 \equiv 0 \pmod{13}\).
\(x^2 \equiv 1\pmod{12}\).
\(7x^2 \equiv 1\pmod{18}\).
\(4x^2 \equiv 7 \pmod{11}\).
Resuelve la siguientes congruencias.
\(x^2\equiv 10\pmod{13^3}\).
\(x^2\equiv 17\pmod{19^2}\).
\(x^2\equiv 25\pmod{128}\).
\(x^2\equiv 41\pmod{256}\)
Verifica que las congruencias \(x^2 \equiv 3\pmod{7}\) y \(x^2\equiv 5\pmod{7}\) no tienen solución, pero la congruencia \(x^2\equiv 15\pmod{7}\) sí tiene solución.
Encuentra todas la soluciones de la congruencia \(x^2\equiv 207\pmod{1001}\).
Demuestra que, si \(a\equiv 1\pmod{8}\) y \(n\ge 3\), entonces la congruencia \(x^2\equiv a\pmod{2^n}\) tiene exactamente \(4\) soluciones incongruentes módulo \(2^n\).