Resolviendo congruencias simultáneas

Question

Tratando de averiguar cómo resolver la congruencia lineal siguiendo la solución de ejemplo al siguiente problema:

$x \equiv 3$ (mod $7$)
$x \equiv 2$ (mod $5$)
$x \equiv 1$ (mod $3$)

Sea:
$n_1$ = 7
$n_2 = 5$
$n_3 = 3$

$N = n_1 \cdot n_2 \cdot n_3 = 105$

$m_1 = \frac{N}{n_1} = 15$

$m_2 = \frac{N}{n_2} = 21$

$m_3 = \frac{N}{n_3} = 35$

$gcd(m_1,n_1)$ = $gcd(15,7) = 1 = 15 \times 1 - 7 \times 2$ por lo que $y_1 = 1$ y $x_1 = 15$
$gcd(m_2,n_2)$ = $gcd(21,5) = 1 = 21 \times 1 - 5 \times 4$ por lo que $y_2 = 1$ y $x_2 = 21$
$gcd(m_3,n_3)$ = $gcd(35,3) = 1 = -35 \times 1 + 3 \times 12$ por lo que $y_3 = -1$ y $x_3 = -35

Hasta este punto entiendo, pero la siguiente línea no la entiendo:

Entonces $x = 15 \times 3 + 21 \times 2 - 35 \times 1 \equiv 52$ (mod $105$)

¿De dónde vienen los $\times 3$, $\times 2$, $\times 1$? ¿Es simplemente porque hay 3 términos, entonces comienza desde 3 luego 2 y luego 1? ¿Y de dónde viene el 52?

Answer 1

Los $3, 2, 1$ son del lado derecho de tus congruencias.

Sabemos que $x=3$ es una solución para la primera congruencia, pero esto no funciona como solución para las siguientes 2 congruencias. Así que el teorema chino del resto te dice que calcules $(3\cdot 5)^{-1}=15^{-1}$ mod $7$. Encuentras que esto es $1$ (ya que $15(1)+(-2)7=1$). Por lo tanto $x=3\cdot 15\cdot 1$ ($=3 \cdot 15 \cdot 15^{-1} = 3 \cdot 1 =3$ (mod 7) sigue siendo una solución de $x \equiv 3 \;\mathrm{mod}\; 7$ ya que $15\cdot 1 \equiv 1 \;\mathrm{mod}\;7$. ¿Qué tiene de especial esta solución? Bueno, $x=3\cdot 15\cdot 1$ también es congruente con 0 módulo $3$ y $5$ (por eso estábamos calculando $(3\cdot 5)^{-1}=15^{-1}$).

Luego, $x=2$ resuelve $x\equiv 2\;\mathrm{mod}\;5$, pero nuevamente no resuelve las otras dos congruencias. Entonces calculas $(3\cdot 7)^{-1}=21^{-1}$ mod $5$. Encuentras que esto es $1$ (ya que $21(1)+5(-4)=1$). Por lo tanto $x=2\cdot 21\cdot 1$ sigue siendo una solución de $x \equiv 2\;\mathrm{mod}\; 5$ mientras también es congruente con 0 módulo $3$ y $7$. Así que ahora hemos encontrado una solución para la segunda congruencia que no interfiere con las primeras y últimas congruencias.

Finalmente, $x=1$ resuelve la tercera congruencia pero no las primeras dos. Así que calculas $(5 \cdot 7)^{-1}=35^{-1}$ mod $3$. Encuentras que esto es $-1$ (ya que $35(-1)+3(12)=1$). Por lo tanto $x=1\cdot 35 \cdot (-1)$ sigue siendo una solución de $x\equiv 1\;\mathrm{mod}\;3$ mientras es congruente con $0$ módulo $5$ y $7.

Entonces ahora cada congruencia tiene una solución que no interfiere con las otras congruencias. Por lo tanto, sumar las soluciones juntas resolverá las 3 al mismo tiempo.

Por lo tanto, $x = 3\cdot 15\cdot 1 + 2\cdot 21\cdot 1 + 1\cdot 35 \cdot (-1) = 45+42-35=52$ es una solución para las 3 congruencias. Dado que $105$ ($=3\cdot 5 \cdot 7$) es $0$ modulo $3$, $5$, y $7$, añadiendo múltiplos de $105$ seguirá dejándonos con una solución para todas las $3$ congruencias.

Answer 2

$2x \equiv -1\,$ mod $\,3,5,7\ \begin{array}{r} \iff 3,5,7\mid 2x\!+\!1\!\\ \iff\ \ \ 105\mid 2x\!+\!1\end{array}\!\iff\!$ mod $\,105\!:\ 2x \equiv -1\equiv 104\!\iff\! x\equiv 52 $

$2x \equiv -1\,$ mod $\,3,5,7\ \begin{array}{r}\iff 3,5,7\mid 2x\!+\!1\!\\ \iff\ \ \ 105\mid 2x\!+\!1\end{array}\!\iff\!$ mod $\,105\!:\ 2x \equiv -1\equiv 104\!\iff\! x\equiv 52\ $

Answer 3

Aunque la respuesta de Bill Cook es completamente, 100% correcta (y basada en la prueba del Teorema del Resto Chino), también se puede trabajar con las congruencias sucesivamente; sabemos por el CRT que existe una solución.

Comenzando desde $x\equiv 3\pmod{7}$, esto significa que $x$ es de la forma $x=7k+3$ para algún entero $k$. Sustituyendo en la segunda congruencia, obtenemos $$7k+3 \equiv 2\pmod{5}.$$ Dado que $7\equiv 2\pmod{5}$ y $3\equiv -2\pmod{5}$, esto es equivalente a $2k-2\equiv 2\pmod{5}$. Dividiendo por $2$ (lo cual podemos hacer ya que $\gcd(2,5)=1$) obtenemos $k-1\equiv 1\pmod{5}$, o $k\equiv 2\pmod{5}$. Es decir, $k$ es de la forma $k=5r+2$ para algún entero $r.

Reemplazando esto en $x=7k+3$ tenemos $x=7(5r+2)+3 = 35r + 17$.

Luego reemplazando esto en la tercera (y última) congruencia, obtenemos $$35r + 17\equiv 1\pmod{3}.$$ Ahora, $35\equiv -1\pmod{3}$, $17\equiv -1\pmod{3}$, por lo que esto es lo mismo que $-r-1\equiv 1\pmod{3}$, o $r\equiv -2\equiv 1\pmod{3}$. Es decir, $r$ es de la forma $3t+1$. Reemplazándolo en $x$ obtenemos $$x = 35r+17 = 35(3t+1)+17 = 105t + 52,$$ así que esto significa que $x$ es de la forma $x=52+105t$ para algún entero $t$; es decir, $x\equiv 52\pmod{105}$ es la solución única módulo $3\times5\times 7$.

Answer 4

CONSEJO $\rm\quad y\: :=\: x-2 \equiv 0\pmod 5\ $ entonces $\rm\: y = 5\:j\:.\ $ Por lo tanto

$\rm\ mod\ 3\!:\ {-}1\equiv y = 5\:j \equiv -j\ \Rightarrow\ j\equiv 1\ \Rightarrow\ y = 5\:(1+3\:k) = 5 + 15\:k$

$\rm\ mod\ 7\!:\ \ \ \ 1 \equiv y = 5 + 15\:k\equiv -2 + k\ \Rightarrow\ k\equiv 3\ \Rightarrow\ y = 5+15\:(3+7\:n) = 50 + 105\:n$

NOTA $\ $ La explotación de la "ley de los números pequeños" a menudo ofrece soluciones más rápidas que la aplicación mecánica de algoritmos (Teorema chino del resto, algoritmo euclidiano extendido, formas normales de Hermite-Smith, etc).

Answer 5

Bueno, utilicé un enfoque diferente que implica crear una A.P., crear 3 ecuaciones como se muestra a continuación y resolverlas. Ahora bien, eso me da infinitas soluciones. Con razón, porque 52 es solo un número que podemos rastrear, de los muchos números que existen y siguen este criterio.

Heads up, esta podría no ser una solución factible y muchos la votarán en contra por eso :)

Aquí va:

Si $x=3(\mod 7)$

Entonces, x es parte de la serie $10,17,24,31,38,45,52...

que es una A.P. con $T1_n=10+(n-1)7$

Si $x=2(\mod 5)$

Entonces, x es parte de la serie $7,12,17,22,27...

que es una A.P. con $T2_n=7+(n-1)5$

Si $x=1(\mod 3)$

Entonces, x es parte de la serie $4,7,10,13,16..

que es una A.P. con $T3_n=4+(n-1)3$

Todo lo que queda es encontrar términos comunes entre estas 3 series. Así que si asumimos que el término $n^{th}$ de la primera secuencia es similar al término $k^{th}$ de la segunda secuencia y al término $p^{th}$ de la tercera secuencia. Entonces,

$7n+3=5k+2 \\ \implies 7n+0p-5k=-1 \\ 5k+2=3p+1 \\ \implies 0n-3p+5k=-1 \\ 3p+1=7n+3 \\ \implies 3p-7n+0k=2$

Obviamente, esto dará infinitas soluciones.

Entonces usamos un enfoque diferente para resolver estas ecuaciones en base a una suposición. Observando la primera ecuación, $k$ tiene que ser mayor que $n$ y $49-50=-1$ sigue esa ecuación. Entones, $n=7$ y $k=10$ es una solución.

Usando, $k=10$ nos da $p=17$.

Entonces, $T1_7=T2_{10}=T3_{17}$

que es $52

)