Resolviendo congruencias

Question

Tengo el siguiente sistema de congruencia:

\begin{align*} I \quad 2x \equiv 0\mod 7 \\ II \quad x \equiv 1 \mod 5\\ III \quad x \equiv 3 \mod 4 \end{align*}

Ahora traté de resolverlo:

\begin{align*} II \quad &x \equiv 1 \mod 5 \Rightarrow x=5x_1+1\\ \stackrel{I}{\Rightarrow} 2(5x_1+1) &\equiv 0 \mod 7 \\ \Leftrightarrow 10x_1+2 &\equiv 0 \mod \\ \Leftrightarrow 10x_1 &\equiv -2 \mod 7\\ \Leftrightarrow 10x_1 &\equiv 12 \mod 7\\ \Rightarrow 5x_1 &\equiv 6 \mod 7 \Rightarrow 5x_1=7x_2+6 \end{align*}

y ahora

ps

Este resultado obviamente no es una solución. Si trato de resolverlo con el algoritmo euclidiano, obtendré el resultado correcto. Ahora intento entender por qué la primera idea es incorrecta. En general, entendí la forma de resolver los sistemas de congruencia, pero nunca pensé en por qué funciona.

Cualquier ayuda es apreciada.

Answer 1

Es una buena idea para tratar de un paso peatonal para resolver su problema. He aquí la mía.

Deje $x\in\mathbb{Z}$ ser una solución de su sistema. Entonces existe $a,b,c\in\mathbb{Z}$ tal forma que: $$\begin{cases}2x=7a\\x=1+5b\\x=3+4c.\end{cases}$$ A continuación, debe haber¹: $$\begin{cases}40x=140a\\28x=28+140b\\35x=105+140c\end{cases}$$ Ahora², $3\times40-3\times28-35=1$, por lo tanto: $$x=-3\times28-105+140(3a-3b-c)=-189+140(3a-3b-c),$$ es decir, $$x=91+140(3a-3b-c-2).$$

Por lo tanto, una condición necesaria para $x\in\mathbb{Z}$ a ser una solución del sistema es: $$x=91\mod 140.$$ Ahora es fácil comprobar que esta condición también es suficiente: vamos a $m\in\mathbb{Z}$ y establezca $x=91+140m$. Entonces: $$x=7\times(13+20m)$$ por lo tanto $x=0\mod 7$. $$x=1+5\times(18+28m)$$ por lo tanto $x=1\mod 5$. $$x=3+4\times(22+45m)$$ por lo tanto $x=3\mod 4$.

---

En general he entendido la forma de resolver la congruencia de los sistemas, pero nunca pensé acerca de por qué funciona.

Espero que esto ayude...

---

¹$140$ natural aparece como el mínimo común múltiplo de $4$, $5$ y $7$.

²Tenemos la suerte de encontrar una relación simple, ¿no?

Answer 2

ps

Como$$2x\equiv0\pmod7\iff x\equiv0\pmod7,x\equiv1\pmod5,x\equiv3\pmod4$ son relativamente primos por parejas, podemos aplicar CRT de forma segura

---

De lo contrario,$7,5,4$

Entonces tenemos $x\equiv0\pmod7\implies x=7x_1, x\equiv1\pmod5\implies x=5x_2+1$

Aplicando la propiedad de convergencia de la fracción continua$7x_1=5x_2+1\iff 7x_1-5x_2=1$,$\displaystyle\frac75=1+\frac25=1+\frac1{\dfrac52}=1+\frac1{1+\dfrac12}$

$\displaystyle 7\cdot2-5\cdot3=-1\implies 7x_1-5x_2=5\cdot3-7\cdot2$ que es un número entero

$\displaystyle\iff7(x_1+2)=5(x_2+3)\iff \frac{7(x_1+2)}5=x_2+3$ como $\displaystyle\implies5|7(x_1+2)\iff 5|(x_1+2)$

$5\nmid 7$

¿Puedes tomarlo desde aquí?

Answer 3

Resolviendo la primera y la segunda ecuaciones simultáneamente, obtienes x = 21 mod 35. Resolviendo la segunda y tercera ecuaciones simultáneamente, obtienes x = 11 mod 20. Resolviendo estos dos resultados simultáneamente, obtienes x = 91 mod 140 que te da todo lo posible soluciones.