Sistemas de congruencias lineales (parte 1)#
Introducción#
En el capítulo anterior, con el teorema chino del residuo encontramos la solución de sistemas de congruencias lineales en donde los módulos son primos relativos por pares. En este capítulo, vamos a estudiar sistemas de congruencias lineales en donde los módulos no necesariamente son primos relativos. Veremos la condición para que estos sistemas tengan solución y mostraremos métodos para resolverlos.
Vamos a separar este tema en dos capítulos, en este capítulo sólo veremos los sistemas de congruencias lineales con una variable. En la segunda parte del capítulo veremos la generalización.
Resultados auxiliares#
Teorema 51
Sean \(a,b\) y \(c\) enteros. El máximo común divisor se distribuye sobre el mínimo común múltiplo, es decir
Demostración. Para demostrar la igualdad, vamos a utilizar la Definición 14. Podemos expresar \(a,b\) y \(c\) en su descomposición canónica, donde quizás algunos exponentes son cero.
Ahora, con el Teorema 13 y el Teorema 14 podemos escribir el máximo común divisor y el mínimo común múltiplo en función de la descomposición en primos.
Vamos a expresar el lado izquierdo de la igualdad, es decir \((a,[b,c])\). Primero calcularemos \([b,c]\), y después \((a, [b,c])\).
Por otro lado, podemos expresar el lado derecho de la igualdad, es decir \([(a,b),(a,c)]\). Primero calcularemos \((a,b)\) y \((a,c)\) y después \([(a,b),(a,c)]\).
Entonces tendríamos que
Para que las expresiones sean iguales, tendríamos que ver que para cada primo \(p_i\) en donde \(1 \le i \le k\), se cumple que
Vamos a considerar los siguientes casos
Supongamos que \(e_i \le max\{f_i,g_i \}\). Entonces tendríamos que
\[min\{e_i, max\{f_i,g_i \} \} = e_i.\]
Por otro lado, sin pérdida de generalidad supongamos que \(max\{f_i, g_i \} = f_i\), entonces tendríamos que \(e_i < f_i\). Queremos ver que pasa con la expresión
Por lo anterior ya tendríamos que \(min\{e_i,f_i \} = e_i\), pero necesitamos ver qué pasa con la expresión \(min\{e_i,g_i \}.\)
Si \(min\{e_i,g_i \} = e_i\), entonces \(e_i < g_i\) y tendríamos que
\[max\{min\{e_i,f_i \} , min\{e_i,g_i \} \} = max \{e_i, e_i \} = e_i.\]Si \(min\{e_i,g_i \} = g_i\), entonces \(g_i < e_i\) y tendríamos que
\[max\{min\{e_i,f_i \} , min\{e_i,g_i \} \} = max \{e_i, g_i \} = e_i.\]
Por lo tanto, en cualquiera de los casos se cumple que
Supongamos ahora que \(e_i > max\{f_i,g_i \}\). Entonces tendríamos que
En este caso \(e_i\) es más grande que \(f_i\) y \(g_i\) sin importar el valor de \(max\{ f_i, g_i \}\), entonces tendríamos que
Entonces la igualdad se cumple para cada primo \(p_i\), en donde \(1\le i\le k\). Así, podemos concluir que \((a,[b,c]) = [(a,b),(a,c)]\). \(\square\)
El teorema Teorema 51 se puede generalizar.
Teorema 52
Sean \(a,b_1,b_2 \ldots b_k\) enteros. El máximo común divisor se distribuye sobre el mínimo común múltiplo de varios enteros, es decir
La demostración es muy parecida a la del Teorema 51 y se dejará como ejercicio al lector.
Sistemas de congruencias lineales de una variable#
En el capítulo anterior estudiamos sistemas de congruencias lineales en donde los módulos necesitaban ser primos relativos por pares para poder poder resolverlos con el Teorema 50. En esta sección vamos a resolver sistemas en donde los módulos no son necesariamente primos relativos.
Teorema 53
El sistema de congruencias lineales
Demostración. Vamos a probar primero que el sistema tiene solución si y sólo si \((m,n)|(a-b)\) y después veremos que esa solución es única módulo \([m,n]\).
Primero veamos que si el sistema tiene solución, entonces \((m,n)|(a-b).\)
Si \(x\) es una solución del sistema, entonces satisface la congruencia \(x\equiv a\pmod{m}\). Por el Teorema 28 tenemos que \(x = a + mu\) para algún entero \(u\). Luego, \(x\) también satisface la congruencia \(x \equiv b\pmod{n}\), entonces tendríamos que
Ahora veamos que si \((m,n)|(a-b)\), entonces el sistema tiene solución.
Por hipótesis tenemos que \((m,n)|(a-b)\). Entonces por la implicación de regreso del Teorema 11 tendríamos que existen enteros \(v\) y \(u\) tales que la ecuación lineal diofantina
Por lo tanto, como \(x = a + mu\), tendríamos que \(x\equiv a\pmod{m}\), y como \(x = b + nv\), tendríamos que \(x\equiv b\pmod{n}\).
Por último vamos a demostrar que la solución es única módulo \([m,n]\).
Supongamos que \((m,n)|(a-b)\) y que \(x_0\) es una solución del sistema de congruencias lineales. Sea \(x_1\) otra solución arbitraria del sistema. Vamos a demostrar que \(x_1\equiv x_0\pmod{[m,n]}\).
Ya que \(x_0\) y \(x_1\) son soluciones, entonces ambas satisfacen las congruencias, es decir que
Luego, por la propiedad \(3\) del Teorema 29, tenemos que \(x_1\equiv x_0\pmod{m}\) y \(x_1\equiv x_0\pmod{n}\), es decir que \(m|(x_1 - x_2)\) y \(n|(x_1 - x_0)\). Por el Corolario 11 tendríamos que \([m,n]|(x_1 - x_0)\), esto significa que \(x_1\equiv x_0\pmod{[m,n]}\).
Así, toda solución es congruente con \(x_0\) módulo \([m,n]\), es decir que la solución es única módulo \([m,n]\). \(\square\)
Aunque del teorema anterior no obtengamos una fórmula para la solución, sí obtenemos una solución particular \(x_0\), la solución general es de la forma \(x = x_0 + [m,n]t\) para algún entero arbitrario \(t\).
Ejemplo 126
Determina si el sistema lineal de congruencias
Solución.
Primero notemos que \((9,12) = 3\). Además \(3|(5-8) = -3\), así el sistema tiene solución.
Como \(x\equiv 5\pmod{9}\), tenemos que \(x = 5 + 9t'\). Esto lo sustituimos en la segunda congruencia:
Por el Lema 12 podemos dividir todos los coeficientes de la congruencia entre \(3\) y tenemos que
Notemos que \(3\cdot 3 \equiv 1\pmod{4}\), entonces tendríamos que
Por lo tanto, tendríamos que
Así, \(x = 32\) es la única solución módulo \(36\) y la solución general es \(x = 32 + 36t\).
Ahora vamos a generalizar el teorema anterior para poder saber cuándo un sistema de \(3\) o más congruencias lineales tiene solución.
Teorema 54
Sea \(k\ge 2\) un entero, el sistema de congruencias lineales
Demostración. Vamos a demostrar las dos implicaciones.
Primero demostremos que si \((m_i,m_j)|(a_i - a_j)\) para toda \(i,j \in \{1,2,\ldots ,k \}\), entonces el sistema tiene solución y además todas las soluciones son congruentes módulo \([m_1,m_2,\ldots ,m_k]\).
Vamos a utilizar inducción sobre el número de congruencias.
Paso base. Si \(k = 2\), tenemos que \((m_1,m_2)|(a_1 - a_2)\) y el sistema
tiene solución y es única módulo \([m_1,m_2]\). Esto ya vimos que es cierto en el Teorema 53.
Hipótesis inductiva. Supongamos que \(k>2\), y que la afirmación es cierta para un sistema de congruencias lineales con \(k-1\) congruencias. Es decir que \((m_i,m_j)|(a_i - a_j)\) para toda \(i,j \in \{1,2,\ldots ,k-1 \}\) y además la solución es única módulo \([m_1,m_2, \ldots ,m_{k-1}]\).
Paso inductivo. Por hipótesis de inducción supondremos que hay una solución \(s\) del sistema de las \(k-1\) primeras congruencias y que las demás soluciones son congruentes módulo \([m_1,m_2, \ldots ,m_{k-1}]\), así que el sistema
Por lo tanto, tendríamos el sistema
Pero por el Teorema 52, como el máximo común divisor se distribuye sobre el mínimo común múltiplo, entonces tenemos que
Para demostrar que \(([m_1,m_2, \ldots ,m_{k-1}], m_k)|(s-a_k)\), tenemos que demostrar cada una de las divisibilidades \((m_i,m_k)|(s - a_k)\) para toda \(1 \le i < k\).
Como \(s\) es solución de cada \(x\equiv a_i\pmod{m_i}\), tendríamos que \(s = a_i + km_i\), que es lo mismo que \(a_i = s - km_i\). Por otro lado, tenemos por hipótesis lo siguiente
Lo anterior quiere decir que
Ahora veamos que si el sistema de congruencias lineales tiene solución, entonces \((m_i,m_j)|(a_i - a_j)\).
Esto sucede ya que para que el sistema tenga solución, cada pareja de congruencias debe tener solución. Entonces la pareja de congruencias
Por el Teorema 53 sabemos que el sistema tiene solución si y solo si \((m_i,m_j)|(a_i - a_j)\). Esto pasa para toda \(i,j\) en donde \(1\le i <j \le k\). \(\square\)
Si obtenemos una solución para el sistema de congruencia, la solución general esta dada por \(x = x_0 + [m_1,m_2,\ldots , m_k]t\), para algún entero arbitrario \(t\).
Ejemplo 127
Resuelve el siguiente sistema de congruencias.
Solución.
Primero tenemos que verificar si las congruencias tienen solución \(2\) a \(2\), es decir, que \((m_i,m_j)|(a_i - a_j)\) para \(i,j\in \{1,2,3,4 \}\).
Para las congruencias \(1\) y \(2\), tenemos
Por lo tanto el sistema tiene solución. Vamos a resolver el sistema por el método de iteración.
De la congruencia \(x\equiv 2\pmod{6}\) tenemos que \(x = 2 + 6t_1\). Sustituyendo esto en la congruencia \(x\equiv 5\pmod{9}\) tenemos que
Ahora, de la congruencia \(t_1 \equiv 2\pmod{3}\), tenemos que \(t_1 = 2 + 3t_2\). Entonces tendríamos que
Ahora, de la congruencia \(t_2 \equiv 7\pmod{11}\), tenemos que \(t_2 = 7 + 11t_3\). Entonces tendríamos que
Entonces de la congruencia \(t_3 \equiv 2\pmod{5}\) tendríamos que \(t_3 = 2 + 5t_4\) y así
Por lo tanto tenemos que la solución general es \(x = 536 + 990t_4\), donde \(t_4\) es un entero arbitrario.
Código para resolver un sistema de congruencias lineales#
Vamos a crear un código que nos ayude a resolver sistemas de congruencias lineales. Las congruencias del sistema son de la forma \(x\equiv a_i\pmod{m_i}\), donde \(a_i\ge 0\) y \(m_i > 0\). Éstas se van a representar en el código como
congruencia = [a_i,m_i]
Primero vamos a crear un código que nos diga si el sistema de congruencias tiene solución, éste código va a recibir como argumento una lista de las congruencias involucradas en el sistema a resolver, es decir, si tenemos un sistema de \(4\) congruencias se representaría como en el siguiente código.
congruencias = [ [a_1,m_1], [a_2,m_2], [a_3,m_3], [a_4,m_4] ]
Utilizaremos el código para calcular el máximo común divisor.
def algoritmo_euclides(a,b):
if a == 0 or b == 0:
return a + b
while (a % b) != 0:
a_1, b_1 = a, b
a = b_1
b = a_1 % b_1
return b
El siguiente código nos ayuda a comprobar si un sistema de congruencias lineales dado, tiene o no solución. El código utiliza la condición del Teorema 54 para verificar si el sistema de congruencias lineales tiene solución.
def tiene_solucion(congruencias):
for i in range(len(congruencias)):
for j in range(i+1, len(congruencias)):
a_i, m_i = congruencias[i]
a_j, m_j = congruencias[j]
if (a_i - a_j) % algoritmo_euclides(m_i, m_j) != 0:
return False
return True
Vamos a modificar el código que creamos en el capítulo de resolución de congruencias lineales para encontrar una solución de una congruencia lineal. Estos cambios serán explicados más adelante.
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 congr_lin_sol (a,b,m):
if a >= m or a < 0:
a = a%m
if b >= m or b < 0:
b = b%m
d_1 = algoritmo_euclides(a,b)
d_2 = algoritmo_euclides(d_1,m)
d_3 = algoritmo_euclides(a,m)
if b == 0 and d_3 > 1:
a, b, m = a//d_3, b, m//d_3
elif b == 0:
return [0,m]
elif d_2 > 1:
a, b, m = a//d_2, b//d_2, m//d_2
elif d_2 == 1 and d_1 > 1:
a, b, m = a//d_1, b//d_1, m
s,t,d = euclides_extendido_ciclos(a,m)
if b%d == 0:
x_0 = (s * (b // d))%m
return [x_0,m]
else:
print(f"La congruencia {a}x ≡ {b} (mod {m}) no tiene solución ")
El siguiente código nos ayuda a resolver un sistema de congruencias lineales.
def resolver_sist_congr(congruencias):
if not tiene_solucion(congruencias):
return print("El sistema no tiene solución")
solucion_final = congruencias[0]
for i in range(1, len(congruencias)):
a,b,m = [solucion_final[1], congruencias[i][0] - solucion_final[0], congruencias[i][1]]
x_0, m = congr_lin_sol(a,b,m)
solucion_final = [solucion_final[0] + solucion_final[1]*x_0, solucion_final[1]*m]
return print("Una solución general del sistema es: ",solucion_final[0], "+",solucion_final[1],"t")
congruencias = [[2, 6], [5, 9], [8, 11], [11, 15]]
resolver_sist_congr(congruencias)
Una solución general del sistema es: 536 + 990 t
congruencias = [[3,4],[5,7]]
resolver_sist_congr(congruencias)
Una solución general del sistema es: 19 + 28 t
congruencias = [[8,5], [5,3], [11,7], [2,4]]
resolver_sist_congr(congruencias)
Una solución general del sistema es: 158 + 420 t
congruencias = [[4,6], [2,8], [1,9]]
resolver_sist_congr(congruencias)
Una solución general del sistema es: 10 + 72 t
congruencias = [[0,4], [3,5]]
resolver_sist_congr(congruencias)
Una solución general del sistema es: 8 + 20 t
Explicación del código#
En esta sección vimos por primera vez el operador lógico not. Este operador se usa para negar una expresión booleana.
a = True
b = not a
En el ejemplo anterior, el valor de la variable «b» sería False.
Ahora veamos las modificaciones a los códigos que ya habíamos construido en capítulos anteriores.
Primero veamos el código que usamos para calcular el máximo común divisor de dos enteros.
Código anterior.
def algoritmo_euclides(a,b):
while (a % b) != 0:
a_1, b_1 = a, b
a = b_1
b = a_1 % b_1
return b
Código modificado.
def algoritmo_euclides(a,b):
if a == 0 or b == 0:
return a + b
while (a % b) != 0:
a_1, b_1 = a, b
a = b_1
b = a_1 % b_1
return b
El código anterior no aceptaba que alguno de los argumentos fuera cero. Si el argumento «b» es igual a cero, el código se detenía por el error de división entre cero. Para corregir ese error agregamos una condición con la idea de que, para cualquier entero \(a\), \((a,0) = a\).
if a == 0 or b == 0:
return a + b
Ahora, veamos las modificaciones al código para resolver congruencias lineales.
Código anterior.
def congr_lin_sol (a,b,m):
if a >= m or a < 0:
a = a%m
if b >= m or b < 0:
b = b%m
s,t,d = euclides_extendido_ciclos(a,m)
if b%d == 0:
x_0 = (s * (b // d))%m
if d == 1:
print(f"La única solución incongruente de la congruencia {a}x ≡ {b} (mod {m}) es x = {x_0%m} ")
else:
print(f"La congruencia {a}x ≡ {b} (mod {m}) tiene {d} soluciones incongruentes")
print("Las soluciones son:")
for i in range(0,d):
print(f"x_{i} = {(x_0 + (m//d)*i)%m}")
else:
print(f"La congruencia {a}x ≡ {b} (mod {m}) no tiene solución ")
Código modificado.
def congr_lin_sol (a,b,m):
if a >= m or a < 0:
a = a%m
if b >= m or b < 0:
b = b%m
d_1 = algoritmo_euclides(a,b)
d_2 = algoritmo_euclides(d_1,m)
d_3 = algoritmo_euclides(a,m)
if b == 0 and d_3 > 1:
a, b, m = a//d_3, b, m//d_3
elif b == 0:
return [0,m]
elif d_2 > 1:
a, b, m = a//d_2, b//d_2, m//d_2
elif d_2 == 1 and d_1 > 1:
a, b, m = a//d_1, b//d_1, m
s,t,d = euclides_extendido_ciclos(a,m)
if b%d == 0:
x_0 = (s * (b // d))%m
return [x_0,m]
else:
print(f"La congruencia {a}x ≡ {b} (mod {m}) no tiene solución ")
El código anterior resuelve congruencia de la forma \(ax\equiv b\pmod{m}\). En esta ocasión agregamos varias condiciones y variables,
d_1 = algoritmo_euclides(a,b)
d_2 = algoritmo_euclides(d_1,m)
d_3 = algoritmo_euclides(a,m)
if b == 0 and d_3 > 1:
a, b, m = a//d_3, b, m//d_3
elif b == 0:
return [0,m]
elif d_2 > 1:
a, b, m = a//d_2, b//d_2, m//d_2
elif d_2 == 1 and d_1 > 1:
a, b, m = a//d_1, b//d_1, m
En primer lugar agregamos las variables «d_1», «d_2» y «d_3» las cuales contienen \((a,b)\), \(((a,b),m)\) y \((a,m)\) respectivamente. Estos valores los calculamos antes ya que se usan en los condicionales if, elif, else.
El primero condicional if es un caso particular del Teorema 31. Lo que queremos lograr con este condicional es que se simplifique la congruencia y por lo tanto el módulo se reduzca.
El segundo condicional, elif, resuelve el caso cuando la congruencia es de al forma \(ax\equiv 0\pmod{m}\). La versión anterior del código ignoraba este caso, pero en esta ocasión necesitamos que nos regrese el valor de cero como solución.
El tercer condicional, elif, es el caso general del Teorema 31. De igual manera lo ocupamos para simplificar la congruencia.
En el cuarto condicional, elif, usamos el Corolario 9 para simplificar la congruencia.
Si ninguno de los casos anteriores se cumple, los valores de «a»,»b» y «m» no se modifican.
Estas condiciones nos ayudan para seguir el algoritmo del Ejemplo 127, y que la solución quede de la forma \(x = x_0 + [a_1,a_2, \ldots ,a_n] t\).
Ahora, veamos cómo funciona el código para comprobar si un sistema de congruencia lineales tiene solución.
def tiene_solucion(congruencias):
for i in range(len(congruencias)):
for j in range(i+1, len(congruencias)):
a_i, m_i = congruencias[i]
a_j, m_j = congruencias[j]
if (a_i - a_j) % algoritmo_euclides(m_i, m_j) != 0:
return False
return True
Definimos una función llamada «tiene_solucion», esta recibe como argumento una lista de listas que contienen los coeficientes de las congruencias.
def tiene_solucion(congruencias):
Luego, comenzamos un ciclo
forel cual con la variable «i», recorremos los valores de \(0\) hasta la longitud de la lista dada. Dentro, creamos otro cicloforel cual con la variable «j», recorremos los valores de \(i+1\) hasta la longitud de la lista.
for i in range(len(congruencias)):
for j in range(i+1, len(congruencias)):
Con los ciclos creados, vamos tomando los coeficientes de la congruencias para verificar si se cumple al condición del Teorema 54. Si en algunos de los casos no se cumple que \((m_i,m_j)|(a_i - a_j)\), el código entra en un condicional
ifque nos regresa el valor deFalse, lo cual quiere decir que el sistema no tiene solución. En caso contrario, si todos los casos satisface la condición, nos regresa un valor de `True, lo cual quiere decir que el sistema sí tiene solución.
a_i, m_i = congruencias[i]
a_j, m_j = congruencias[j]
if (a_i - a_j) % algoritmo_euclides(m_i, m_j) != 0:
return
return True
Por último, veamos el código que usamos para resolver un sistema de congruencias lineales.
def resolver_sist_congr(congruencias):
if not tiene_solucion(congruencias):
return print("El sistema no tiene solución")
solucion_final = congruencias[0]
for i in range(1, len(congruencias)):
a,b,m = [solucion_final[1], congruencias[i][0] - solucion_final[0], congruencias[i][1]]
x_0, m = congr_lin_sol(a,b,m)
solucion_final = [solucion_final[0] + solucion_final[1]*x_0, solucion_final[1]*m]
return print("Una solución general del sistema es: ",solucion_final[0], "+",solucion_final[1],"t")
Definimos una función llamada «resolver_sist_congr» la cual recibe como argumento una lista de listas que contienen los coeficientes de la congruencias.
def resolver_sist_congr(congruencias):
Luego empezamos un condicional
if, el cual se ejecuta si el sistema no tiene solución. Si la función «tiene_solución» no regresa como resultadoFalse, tenemos que usar el operador lógiconotpara convertir el resultado enTruey que se ejecute el código dentro del condicionalif. Esto nos imprimiría en pantalla que el sistema no tiene solución y se terminaría el código.
if not tiene_solucion(congruencias):
return print("El sistema no tiene solución")
Si el sistema tiene solución entonces el código continua con la siguiente parte.
Creamos la variable «cgr_1», la cual toma como valor los coeficientes de la primera congruencia en el sistema.
Luego, comenzamos un cicloforel cual tiene como rango de \(1\) hasta la longitud de la lista. Siguiendo el algoritmo del Ejemplo 127, tendríamos que la congruencia \(x\equiv a_i\pmod{m_i}\) se pasa a la forma \(x = a_i + km_i\), para algún entero \(k\). El valor de \(x\) se sustituye en la siguiente congruencia y se resuelve para conseguir un resultado. Este proceso se va repitiendo hasta que terminemos con las congruencias y obtengamos la solución \(x = x_0 + [m_1,m_2, \ldots ,m_n] t\), para algún entero \(t\).
Con la primer líneaa,b,m = [solucion_final[1], congruencias[i][0] - solucion_final[0], congruencias[i][1]]lo que logramos es la sustitución del valor \(x\) en la congruencia y se crea la congruencia a resolver. Los valores dentro de la lista se asignan a las variables «a», «b» y «m».
Con la líneax_0, m = congr_lin_sol(a,b,m), obtenemos la solución de la congruencia anterior. Asignamos la solución a la variable «x_0» y el módulo que se trabajó a la variable «m». Luego en la tercera líneasolucion_final = [solucion_final[0] + solucion_final[1]*x_0, solucion_final[1]*m], lo que hacemos es ir actualizando el valor de la variable \(x\) que es el que se va sustituyendo en cada iteración.
Finalmente, el código nos imprime en pantalla la solución general del sistema de la forma \(x = x_0 + [m_1,m_2, \ldots ,m_n] t\).
solucion_final = congruencias[0]
for i in range(1, len(congruencias)):
a,b,m = [solucion_final[1], congruencias[i][0] - solucion_final[0], congruencias[i][1]]
x_0, m = congr_lin_sol(a,b,m)
solucion_final = [solucion_final[0] + solucion_final[1]*x_0, solucion_final[1]*m]
return print("Una solución general del sistema es: ",solucion_final[0], "+",solucion_final[1],"t")
Ejercicios de práctica#
Demuestra el Teorema 52.
Determina si los siguientes sistemas de congruencias lineales tienen solución.
\(x\equiv 2\pmod{10}\) y \(x\equiv 7\pmod{15}\).
\(x\equiv 4\pmod{9}\), \(x\equiv 10\pmod{12}\) y \(x\equiv -2\pmod{18}\).
\(x\equiv 7\pmod{8}\), \(x\equiv 3\pmod{10}\) y \(x\equiv 2\pmod{15}\).
Resuelve los siguientes sistemas de congruencias.
\(x\equiv 10\pmod{12}\) y \(x\equiv 4\pmod{15}\).
\(x\equiv 1\pmod{10}\), \(x\equiv 5\pmod{12}\) y \(x\equiv -4\pmod{15}\).
\(x\equiv 2\pmod{6}\), \(x\equiv 5\pmod{7}\), \(x\equiv 6\pmod{8}\) y \(x\equiv 8\pmod{9}\).
Encuentra el menor entero \(n\ge 3\) tal que \(2|n\), \(3|n+1\), \(4|n+2\), \(5|n+3\) y \(6|n+4\).