¿Cómo reducir los sistemas de congruencia con módulos no coprimos?

Question

Me dan un sistema de congruencias y quiero aplicar el teorema del resto chino (TRC) sobre él, pero el máximo común divisor (MCD) de los módulos no es $1$ .

Bueno, necesito reducir el sistema, de tal manera que el GCD es $1$ pero no sé cómo funciona la "reducción". Quiero decir que necesito una explicación.

Encontré un ejemplo, pero no entiendo cómo lo transforman mágicamente de

$$x \equiv 1 \mod 108$$ $$x \equiv 13 \mod 40$$ $$x \equiv 28 \mod 225$$

a $$x \equiv 1 \mod 27$$ $$x \equiv 5 \mod 8$$ $$x \equiv 3 \mod 25$$

Veo que $$108 = 2^2 \times 3^3$$ $$ 40 =5 \times 2^3$$ $$225=3^2 \times 5^2$$

pero no estoy seguro de cuándo y cómo lo usaron... ¡gracias por la ayuda!

Answer 1

Esencialmente tienes que descubrir congruencias que signifiquen más o menos lo mismo.

Por ejemplo, si $x \equiv 1 \bmod 108$ entonces $x \equiv 1 \bmod 3$ también. Sin embargo, no es necesario dividir $108$ tanto, ya que al dividir el $4$ para conseguir $x \equiv 1 \bmod 27$ es suficiente para que el primer módulo sea coprimo de los otros dos módulos.

Ahora sólo tienes que hacer los módulos $40$ y $225$ coprime. Usted podría dividir la $25$ de $225$ y entonces el tercer módulo es coprimo del segundo, pero no del primero.

Por lo tanto, la opción más directa en este punto es dividir el $5$ de $40$ y dividir el $9$ de $225$ , dándole a usted $8$ y $25$ para el segundo y tercer módulo.

Pero cuidado: desde $13 > 8$ y $28 > 25$ , tienes que cambiar esos dos restos. Bueno, técnicamente no tienes que hacerlo, pero algunas implementaciones del algoritmo podrían ser lanzadas y no entregar el resultado correcto, o ningún resultado en absoluto.

Así, $x \equiv 13 \bmod 40$ se convierte en $x \equiv 5 \bmod 8$ (ya que $13 - 8 = 5$ ) y $x \equiv 28 \bmod 225$ se convierte en $x \equiv 3 \bmod 25$ (ya que $28 - 25 = 3$ ).

Para comprobar tus respuestas en Wolfram Mathematica o Wolfram Alpha: haz ChineseRemainder[{1, 13, 28}, {108, 40, 225}] y comparar los resultados con ChineseRemainder[{1, 5, 3}, {27, 8, 25}] (dependiendo de circunstancias ajenas a su control, Wolfram Alpha puede no dar un resultado cuando los módulos no son coprimos).

$x = 2053$ ya que $2053 = 19 \times 108 + 1 = 51 \times 40 + 13 = 9 \times 225 + 28$ . También $2053 = 76 \times 27 + 1 = 256 \times 8 + 5 = 82 \times 25 + 3$ .

(Sólo quería probar ese texto "invisible hasta pasar el cursor" que veo en tantas respuestas en este sitio).

Answer 2

Reducir es trivial:

Si $a \equiv b \mod n$ entonces $a \equiv b \mod k$ para todos $k|n$ .

Piensa en ello......

\=======

$x \equiv 1 \mod 108 \implies x= 108k + 1 = 27(4k) + 1 \implies x \equiv 1 \mod 27$ .

$x \equiv 13 \mod 40 \implies x = 40k + 13 = 8(5k) + 13 \implies x \equiv 13 \equiv 5 \mod 8$ . etc.

\=======

Va el otros manera que requiere una estipulación (menor).

Si $a \equiv b \mod k$ entonces $a \equiv b + ck \mod n$ para cualquier $n$ un múltiplo de $k$ y $c$ es algún número entero; (no se sabe exactamente qué número entero).

\====

Así que $x \equiv 1 \mod 3^3*2^2$

$x \equiv 13 \mod 2^3*5$

$x \equiv 28 \mod 5^2*3^2$

Elige el mayor de los factores primos mutuos: $3^3;2^3;5^2$

Así que

$x \equiv 1 \mod 3^3$

$x \equiv 13\mod 2^3$

$x \equiv 28 \mod 2^5$ .

Answer 3

La idea es utilizar la TRC para dividir las congruencias en equivalente congruencias a potencias primarias, y luego eliminar las congruencias redundantes (mostradas como implicaciones de flechas arriba y abajo)

$\begin{array}{lll} x\equiv1 \pmod{\!2^2\cdot 3^3}\iff &\!\!\!\!\!\!\color{#0a0}{x\equiv1} \pmod{\!2^2}, &\!\!\!\!\!\! x\equiv 1\pmod{\!3^3}\\[-.5em] & \Uparrow & \\[-.3em] x\equiv 13 \pmod{\!2^3\cdot 5}\iff &\!\!\!\!\!\!\color{#c00}{x\equiv 13\equiv5} \pmod{\!2^3}, & \Downarrow&x\equiv 13\equiv3\pmod{\!5}\\[-.5em] & & & \quad \Uparrow\\[-.2em] x\equiv28\pmod{\!3^3\cdot 5^2}\!\iff &&\!\!\!\!\!\!x\equiv28\equiv1\pmod{\!3^2}, &x\equiv 28\equiv 3\pmod{\!5^2} \end{array}$

Por ejemplo, nota $\,\color{#c00}{x\equiv 5}\pmod{\!2^3}\,\Rightarrow\, \color{#0a0}{x\equiv 5\equiv 1}\pmod{\!2^2},\,$ por lo que esta última es redundante y puede ser eliminada.

Del mismo modo, podemos eliminar las congruencias implícitas mod $3^2$ y mod $5,\,$ dejando dicho equivalente sistema de tres congruencias a potencias primarias.

Answer 4

Los primos que dividen al menos uno de los tres módulos son $2$ , $3$ y $5$ .

El mayor poder de $2$ en cualquiera de ellos es $2^3 = 8$ que divide $40$ . Dado que $x \equiv 13 \mod 40$ , $x \equiv 13 \equiv 5 \mod 8$ . También tiene $x \equiv 1 \mod 108$ lo que implica $x \equiv 1 \mod 4 (=2^2)$ y esto no es un problema ya que $5 \equiv 1 \mod 4$ .

Del mismo modo, la mayor potencia de $3$ es $3^3 = 27$ ; $x \equiv 1 \mod 108$ así que $x \equiv 1 \mod 27$ y esto es compatible con $x \equiv 28 \mod 225$ desde $28 \equiv 1 \mod 3^2$ .

Por último, la mayor potencia de $5$ es $5^2 = 25$ ; $x \equiv 28 \mod 225$ implica $x \equiv 28 \equiv 3 \mod 25$ y esto es compatible con $x \equiv 13 \mod 40$ porque $13 \equiv 3 \mod 5$ .