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.