Mínimo común múltiplo de 3 ecuaciones modulares

Question

i%7=1   ->  i=1+7n
i%9=2   ->  i=2+9n
i%11=3  ->  i=3+11n

Además de escribir todo:

1,8,15,22...
2,11,20,29...
3,14,25,36...

para encontrar el LCM. ¿Hay alguna forma mejor de hacerlo?

Answer 1

En general, se debe utilizar el Teorema chino del resto.

Sin embargo, para estos particular números, ¡hay un truco! Obsérvese que las congruencias son equivalentes a $2x+5\equiv 0\pmod{7}$ , $2x+5\equiv 0\pmod{9}$ y $2x+5\equiv 0\pmod{11}$ . Así que queremos $2x+5$ sea divisible por $7$ , $9$ y $11$ y, por lo tanto, por $(7)(9)(11)$ que es $693$ . Así que $2x+5=693$ funcionará. Eso da $x=344$ .

Observación: Si no estás familiarizado con la notación de congruencia, observa las secuencias de números que has producido. Nos concentraremos en la primera, que fue $1,8,15,22,\dots$ (hubo un leve error tipográfico).

Doble estos, y añadir $5$ . Obtenemos $7,21, 35, 49,\dots$ , los múltiplos Impares de $7$ . Del mismo modo, al duplicar los números de la segunda secuencia, y sumar $5$ , se obtienen los múltiplos de impar de $9$ . Un tratamiento similar a la tercera secuencia permite obtener los múltiplos Impares de $11$ . Así que queremos $2x+5$ para ser un múltiplo impar de $(7)(9)(11)$ . El menor positivo es $693$ . Así que ahora resuelve $2x+5=693$ .

También se puede llevar a cabo el mismo argumento utilizando el lenguaje de los restos. Queremos $(2x+5)\%7=0$ , $(2x+5)\%9=0$ y $(2x+5)\%11=0$ .

Answer 2

$\begin{eqnarray}\rm {\bf Hint} &&\rm\qquad\ x &\equiv&\rm n\pmod{2n\!+\!5},\ \ n = 1,2,3\\ \Rightarrow &&\rm\ 2x\!+\!5 &\equiv&\rm 0\pmod{2n\!+\!5},\ \ n = 1,2,3 \end{eqnarray}$

Así, $\rm\:7,9,11\: |\: 2x\!+\!5\:\Rightarrow\: lcm(7,9,11) = 693\:|\:2x\!+\!5.\:$

Por lo tanto, $\rm\ mod\ 693\!:\,\ x \,\equiv\, \dfrac{-5}2\,\equiv\, \dfrac{693-5}2 \,\equiv\, 344.$

Nota: La idea se generaliza: véase CCRT para congruencias en A.P. (Progresión Aritmética).