Buscar todos $x\in \mathbb{Z}$ con $x \equiv 2 \mod 4$ , $x \equiv 8\mod9$ y $x \equiv 1\mod5$

Question

Buscar todos $x\in \mathbb{Z}$ con $x \equiv 2 \mod 4$ , $x \equiv 8\mod9$ y $x \equiv 1\mod5$

Mi intento:

$\gcd\left(9,5,4\right) = 1 = 9r+5s+4\times0$

$9 = 1\times5+4$

$5 = 1\times4+1$

así que $1 = 5-(9-5) = 2\times5 - 1\times9$

así $r=-1$ y $s = 2$

así que $x = 2\times5\times8 -1\times9\times1=80 - 9=71\mod 180$

Pero el problema es que $71\equiv8\mod9$ y $71\equiv1\mod5$ pero $71 \ne 2 \mod 4$ . ¿Qué ocurre?

Answer 1

CRT no funciona con los coeficientes de Bezout de todo el sistema : funciona con dos a la vez, pero no con los tres. Por eso el $x$ que obtienes resuelve las dos primeras congruencias, pero no la tercera : porque en realidad hiciste el procedimiento correcto para los dos últimos módulos, pero el tercero se incorporó con el coeficiente $0$ lo cual es incorrecto.

Lo que deberías haber hecho es lo siguiente: resolver las dos últimas juntas observando que $1 = 9r+5s$ con $s = 2$ y $r = -1$ Así, se obtiene $8 \times 5 \times 2 + 9 \times -1 \times 1= 71$ pero sólo módulo $\mathbf{45}$ no todo $180$ . Esto se reduce a $26$ modulo $45$ .

Ahora, resuelve $26 \pmod{45}$ y $2 \pmod{4}$ juntos, observando que $4r + 45s = 1$ donde $s =1$ y $r = -11$ por lo que obtenemos $4 \times -11 \times 26 + 45 \times 1 \times 2 = -1054$ mod $180$ lo que da $26 \mod 180$ (que se podría haber observado a partir de las propias ecuaciones, pero yo resolví sólo para asegurarme).

Ahora, resulta que se pueden hacer todos los coeficientes a la vez : pero para esto, todavía se necesitan tres soluciones de coeficientes de Bezout separadas pero wcon diferentes módulos. Véase aquí para más detalles.

Answer 2

En $x\equiv2\mod4$ , dejemos que $x=4a+2$ que $a$ es un número entero. Luego introdúcelo en la segunda ecuación, $$4a+2\equiv8\mod9\\4a\equiv6\mod9\\2a\equiv3\mod9\\2a\equiv12\mod9\\a\equiv6\mod9$$ Después, hacemos lo mismo: dejamos que $a=9b+6$ que $b$ es un número entero, $x=4\left(9b+6\right)+2=36b+26$ . Luego introdúcelo en la tercera ecuación, $$36b+26\equiv1\mod5\\36b\equiv0\mod5\\b\equiv0\mod5$$ Entonces $b=5k$ que $k$ es un número entero. $x=36\left(5k\right)+26=180k+26$ y esa es la respuesta.

Conclusiones: La respuesta es $180k+26$ para $k\in\mathbb{Z}$ .

Answer 3

Sugerencia $\ \overbrace{x = \color{#0a0}{-1\!+\!9}(a\!+\!5(b\!+\!4c))}^{\text{by iterated division}}\,$ así que $\overbrace{\color{#90f}{\bmod 5}\Rightarrow a\equiv 3}^{\large\color{#90f}{x\ \equiv\ 1}};\ $ $\overbrace{\color{#c00}{\bmod 4}\Rightarrow b\equiv 0}^{\large\color{#c00}{x\ \equiv\ 2}},\,$ así que $\ \bbox[5px,border:1px solid #c00]{x= 26\!+\!180c}$

Observación $ $ Lo que falló en tu método es que no aplicaste correctamente el Fórmula CRT (o has intentado incorrectamente generalizar la fórmula para dos congruencias). Aplicando la fórmula enlazada se obtiene

$\!\begin{align} x\,&\equiv\, \color{#c00}{2\pmod{4}}\ \ \ \ {\rm and}\, \ \ \ x\equiv \color{#0a0}{-1\pmod{9}}\ \ \ \ \ {\rm and}\,\ \ \ \ \ x\equiv \color{#90f}{1\pmod{5}}\\[.5em] \iff x\ &\equiv\, \color{#c00}2(9\cdot 5)\overbrace{((9\cdot 5)^{-1}\!\color{#c00}{\bmod 4)}}^{\large\! 1/45\ \equiv\ \color{#c00}{1/1}\ } \color{#0a0}{-1} (4\cdot 5)\overbrace{((4\cdot 5)^{-1}\!\color{#0a0}{\bmod 9)}}^{\large 1/20\ \equiv\ 10/2\ \equiv\ \color{#0a0}{5/1}} + \color{#90f}1(4\cdot 9)\overbrace{((4\cdot 9)^{-1}\!\color{#90f}{\bmod 5)}}^{\large\! 1/36\ \equiv\ \color{#90f}{1/1}}\\[.5em] &\equiv\, \color{#c00}2(9\cdot 5)\,(\color{#c00}{1/1}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \color{#0a0}{-1} (4\cdot 5)\,(\color{#0a0}{5/1}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \:\! + \color{#90f}1(4\cdot 9)\,(\color{#90f}{1/1})\\[.5em] &\equiv\ \color{#c00}{90}\ \ - \ \ \color{#0a0}{100}\ \ +\ \ \color{#90f}{36}\ \bbox[5px,border:1px solid #c00]{\equiv\, 26\pmod{\!180}} \end{align}$

Véase esta respuesta para una explicación intuitiva de la génesis de la fórmula CRT anterior (que le ayudará a recordarla correctamente y a aplicarla con eficacia).

Answer 4

Estoy utilizando el método para resolver este sistema de ecuaciones como esbozado aquí .

---

Aquí tenemos $a_1 = 2, a_2 = 8, a_3 = 1$ . Además, $n_1 = 4, n_2 = 9, n_3 = 5$ . Ahora, $N = n_1 \cdot n_2 \cdot n_3 = 180$ .

Por lo tanto, $y_1 = 45, y_2 = 20, y_3 = 36$ . Ahora, debemos encontrar los valores de $z_i$ para $i = 1, 2, 3$ . Voy a esbozar el método para encontrar $z_1$ y los demás siguen el mismo camino.

Ahora, $z_1 \equiv 45^{-1} \mod 4$ . Ahora, ¿cuál es el valor de $45^{-1}$ ? Es ese valor de $x \in \mathrm{Z_4}$ tal que $$45x \equiv 1 \mod 4$$ Podemos ver fácilmente que $x = 1$ . Entonces, tenemos: $z_1 \equiv 1 \mod 4$ lo que da $z_1 = 1$ .

---

¿Puedes seguir desde aquí?

Answer 5

He aquí una forma elemental de hacerlo: Desde $x\equiv 2\mod 4$ entonces $x$ es par. Dado que $x\equiv 1\mod 5$ entonces la expansión decimal de $x$ tiene $1$ o $6$ en las unidades. Pero $x$ es par, por lo que debe ser $6$ .

Así que $x=10k+6$ para algunos $k$ . Pero también, $x\equiv 8\mod 9$ por lo que la suma de los algarismos de $x$ es de la forma $9p+8$ . Pero como $x=10k+6$ la suma de los algarismos de $x$ es $k+6$ es decir $$9p+8=k+6$$ así que $k=9p+2$ . Sustituyendo, tenemos $x=10(9p+2)+6=90p+26$ para algunos $p$ .

Pero ahora usamos de nuevo que $x\equiv 2\mod 4$ lo que significa que el resto de la división de $x=90p+26$ por $4$ es $2$ . De esto, $90p$ debe ser divisible por $4$ Así que $p$ es par, digamos $p=2q$ .

Por lo tanto, $x=180q+26$ para algunos $q=0,1,2,\ldots$ . A la inversa, se puede comprobar que cualquier número de esta forma satisface todas las congruencias deseadas.