Si me queda un sistema con dos congruencias donde los modulos no son coprimos entre si, es necesario llevar los modulos a primos y aplicar TCR o no puedo directamente con los modulos no coprimos resolver el sistema?? Si los tengo q llevar a coprimos, es porq el TCR me asegura q la solucion q encuentre va a ser unica??

El libro Aritmética da la respuesta:

Sean y números naturales y sean y enteros. El sistema , es resoluble si y sólo si , donde . En tal caso la solución es única módulo .

Dejo una explicación de por qué es verdad (mía, no confíen):



Si tenés un sistema de más ecuaciones vas haciendo esto con las primeras dos, lo cual te devuelve otra (módulo el mcm de los módulos), con esta nueva y la siguiente, que te da otra, y así siguiendo. Si hay solución y los módulos son entonces es única módulo y hay si y sólo si viendo cada par de ecuaciones, éstas cumplen la condición .

Espero que sirva. Si hay algo mal por favor avisen. Suerte!

Otra demostración de la que sale un algoritmo super eficiente (con lo anterior no quedaba claro que se pudiera resolver en tiempo polinomial).