¿Cuál es la razón por la que solo los módulos coprimos funcionan en el teorema del resto chino? ¿Qué problema surge si se toman módulos no coprimos?

Answer 1

El teorema del resto chino [matemáticas] ([/ matemáticas] CRT [matemáticas]) [/ matemáticas] pide una solución (común) [matemáticas] x [/ matemáticas] a un sistema de congruencias

[matemáticas] x \ equiv \ begin {cases} a_1 \ bmod {m_1} \\ a_2 \ bmod {m_2} \\ a_3 \ bmod {m_3} \\ \ vdots \\ a_k \ bmod {m_k} \ end {cases} \ ldots (\ star) [/ math]

con [math] \ gcd (m_i, m_j) = 1 [/ math] para [math] i \ ne j [/ math]. El teorema establece que hay infinitas soluciones, y cualesquiera dos difieren en un múltiplo de [math] \ text {lcm} (m_1, m_2, m_3, \ ldots, m_k) [/ math].

Si los [math] m_i [/ ​​math] no son coprime por pares, entonces siempre es posible tener sistemas que no admitan soluciones. Por ejemplo, si [math] p [/ math] es primo que divide tanto [math] m_1 [/ math] como [math] m_2 [/ math] y [math] p \ nmid (a_1-a_2) [/ math ], el sistema proporcionado por [math] (\ star) [/ math] no puede tener solución. Después de todo, [math] m_1 \ mid (x-a_1) [/ math] y [math] m_2 \ mod (x-a_2) [/ math] implica, en particular, que [math] p [/ math] divide ambos [matemáticas] x-a_1 [/ matemáticas] y [matemáticas] x-a_2 [/ matemáticas]. Pero entonces [math] p [/ math] debe dividir su diferencia [math] (x-a_1) – (x-a_2) [/ math]. Entonces, al elegir [math] a_1, a_2 [/ math] tal que [math] p \ nmid (a_1-a_2) [/ math], tenemos un sistema sin solución. En otras palabras, siempre existirán sistemas sin solución siempre que haya un par de módulos que compartan un factor común mayor que [math] 1 [/ math].

Por otro lado, también es posible que un sistema dado por [math] (\ star) [/ math] tenga una solución incluso cuando [math] \ gcd (m_i, m_j)> 1 [/ math] para cada par [matemáticas] i, j, [/ matemáticas] [matemáticas] i \ ne j [/ matemáticas]. [matemáticas] \ blacksquare [/ matemáticas]