Teorema chino del resto con módulos no coprimos

Question

Dejemos que $n_1,...,n_k \in \mathbb{N}$ y que $a_1,...,a_k \in \mathbb{Z}$ . Cómo demostrar la siguiente versión del teorema del resto chino ( ver aquí ):

Existe un $x \in \mathbb{Z}$ que satisfaga el sistema de ecuaciones: $$x=a_1 \pmod {n_1}$$ $$x=a_2 \pmod {n_2}$$ $$\ldots$$ $$x=a_k \pmod{n_k}$$ si y sólo si $a_i=a_j \pmod{\gcd(n_i,n_j)}$ para todos $i,j=1,...,k$ ?

Si los números $n_i$ , para $i=1,...,k$ son coprimas entre sí, es una versión clásica del teorema del resto chino.

Gracias.

Answer 1

Si tenemos en cuenta $n_k$ en primos, $n_k = p_{1}^{b_{1}}\cdots p_r^{b_{r}}$ entonces el Teorema Chino del Resto nos dice que $x\equiv a_k\pmod{n_k}$ es equivalente al sistema de congruencias $$\begin{align*} x&\equiv a_k\pmod{p_1^{b_{1}}}\\ x&\equiv a_k\pmod{p_2^{b_{2}}}\\ &\vdots\\ x&\equiv a_k\pmod{p_r^{b_{r}}} \end{align*}$$ Así, podemos sustituir el sistema de congruencias dado por uno en el que cada módulo es una potencia prima, $n_i = p_i^{b_i}$ .

Tenga en cuenta que la suposición de que $a_i\equiv a_j\pmod{\gcd(n_i,n_j)}$ "pasa" por esta sustitución (si fueran congruentes módulo $\gcd(n_i,n_j)$ , entonces también son congruentes módulo de las gcds de las potencias primarias).

Por lo tanto, podemos suponer sin pérdida de generalidad que todo módulo es una potencia prima.

Afirmo que podemos tratar cada primo por separado, de nuevo por el Teorema Chino del Resto. Si podemos resolver todas las congruencias que implican el primo $p_1$ para obtener una solución $x_1$ (que se determinará modulo la mayor potencia de $p_1$ que se produce); y todas las congruencias que implican el primo $p_2$ para obtener una solución $x_2$ (que se determinará modulo la mayor potencia de $p_2$ que se produce); y así sucesivamente hasta obtener una solución $x_n$ para todas las congruencias que implican el primo $p_n$ (determinado modulo la mayor potencia de $p_n$ que se produce), entonces podemos obtener una solución simultánea resolviendo el sistema habitual del Teorema del Resto Chino $$\begin{align*} x &\equiv x_1 \pmod{p_1^{m_1}}\\ &\vdots\\ x &\equiv x_n\pmod{p_n^{m_n}} \end{align*}$$ (donde $m_i$ es la mayor potencia de $p_i$ que se produce como un módulo).

Así que estamos reducidos a resolver si podemos resolver el sistema $$\begin{align*} x &\equiv a_1\pmod{p^{b_1}}\\ x &\equiv a_2\pmod{p^{b_2}}\\ &\vdots\\ x & \equiv a_n\pmod{p^{b_n}} \end{align*}$$ con, sin pérdida de generalidad, $b_1\leq b_2\leq\cdots\leq b_n$ .

¿Cuándo se puede resolver esto? Claramente, esto puede ser resuelto si y sólo si $a_i\equiv a_j\pmod{p^{b_{\min(i,j)}}}$ Cualquier solución debe satisfacer esta condición, y si esta condición se cumple, entonces $a_n$ es una solución.

Por ejemplo: digamos que los módulos originales han sido $n_1 = 2^3\times 3\times 7^2$ , $n_2= 2^2\times 5\times 7$ , $n_3=3^2\times 5^3$ . Primero sustituimos el sistema por el sistema de congruencias $$\begin{align*} x&\equiv a_1 \pmod{2^3}\\ x&\equiv a_2\pmod{2^2}\\ x&\equiv a_1\pmod{3}\\ x&\equiv a_3\pmod{3^2}\\ x&\equiv a_2\pmod{5}\\ x&\equiv a_3\pmod{5^3}\\ x&\equiv a_1\pmod{7^2}\\ x&\equiv a_2\pmod{7}. \end{align*}$$ A continuación, resolvemos los sistemas por separado: $$\begin{align*} x_1&\equiv a_1 \pmod{2^3} &x_2&\equiv a_1\pmod{3}\\ x_1&\equiv a_2\pmod{2^2}&x_2&\equiv a_3\pmod{3^2}\\ \strut\\ x_3&\equiv a_2\pmod{5}&x_4&\equiv a_1\pmod{7^2}\\ x_3&\equiv a_3\pmod{5^3}&x_4&\equiv a_2\pmod{7}. \end{align*}$$

Suponiendo que podamos resolverlos, $x_1$ está determinado por el módulo $2^3$ , $x_2$ modulo $3^2$ , $x_3$ modulo $5^3$ y $x_4$ modulo $7^2$ Así que resolvemos el sistema $$\begin{align*} x &\equiv x_1\pmod{2^3}\\ x &\equiv x_2\pmod{3^2}\\ x&\equiv x_3 \pmod{5^3}\\ x&\equiv x_4\pmod{7^2} \end{align*}$$ y obtener una solución del sistema original.

Por lo tanto, si la condición $a_i\equiv a_j\pmod{\gcd(n_i,n_j)}$ se mantiene en el sistema original, entonces obtenemos una solución para cada primo, y a partir de la solución para cada primo obtenemos una solución del sistema original aplicando dos veces el Teorema del Resto Chino habitual.