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??
Tema
Duda de TCR
El libro Aritmética da la respuesta:
Sean \(m\) y \(n\) números naturales y sean \(a\) y \(b\) enteros. El sistema \(x\equiv a\, (m)\), \(x\equiv b\, (n)\) es resoluble si y sólo si \(a \equiv b\, (d)\), donde \(d=(m:n)\). En tal caso la solución es única módulo \([m:n]\).
Dejo una explicación de por qué es verdad (mía, no confíen):
Obvio que si \(x\) satisface las dos condiciones entonces \(a\equiv b\, (d)\).
Supongamos que \(a\equiv b\, (d)\). La descomposición en primos de \(m\) y \(n\) sea
$$m = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_r^{\alpha_r},$$
$$n = p_1^{\beta_1}p_2^{\beta_2}\ldots p_r^{\beta_r}.$$
(Se entiende que algunos exponentes son cero.)
Definimos
$$d_1 = p_1^{\gamma_1}p_2^{\gamma_2}\ldots p_r^{\gamma_r},$$
$$d_2 = p_1^{\delta_1}p_2^{\delta_2}\ldots p_r^{\delta_r},$$
donde \(\gamma_i\) y \(\delta_i\) se definen así: si \(\alpha_i\leqq \beta_i\) entonces \(\gamma_i = \alpha_i\) y \(\delta_i = 0\); en otro caso \(\gamma_i=0\) y \(\delta_i=\beta_i\).
Tenemos que el exponente de \(p_i\) en la factorización de \(d_1d_2\) es \(\min\{\alpha_i, \beta_i\}\) así que \(d_1d_2=d\). Sean \(m' = m/d_1\) y \(n' = n/d_2\). Tenemos que \((m':n')=1\) (comprobación trivial) y \(m'n'=mn/d=[m:n]\) así que el sistema
$$x\equiv a\, (m'),$$
$$x\equiv b\, (n')$$
tiene solución única módulo \([m:n]\). Veamos que estas soluciones son soluciones del sistema inicial y habremos demostrado el teoremita.
Tenemos que \(d\mid m,n\) así que \(d_1\mid n/d_2=n'\) y \(d_2\mid m/d_1=m'\). Ahora \(n'\mid x-b\) y \(m'\mid x-a\). Entonces \(d_1\mid x-b\) y \(d_2\mid x-a\). Ahora \(d\mid a-b\) así que \(d_1\mid a-b\) y \(d_2\mid a-b\) así que también \(d_2\mid x-b\) y \(d_1\mid x-a\). Ahora se ve fácil que \((m':d_1)=1\) y \((n':d_2)=1\) así que \(m=d_1m'\mid x-a\) y \(n\mid d_2n'\mid x-b\), como queríamos.
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 \(m_1,m_2,\ldots, m_n\) entonces es única módulo \([m_1:m_2:\ldots : m_n]\) y hay si y sólo si viendo cada par de ecuaciones, éstas cumplen la condición \((m_i:m_j)\mid a_i-a_j\).
Espero que sirva. Si hay algo mal por favor avisen. Suerte!
Firma
"En el principio existía la Palabra, y todo era texto." (San Juan Derrida)
Otra demostración de la que sale un algoritmo super eficiente (con lo anterior no quedaba claro que se pudiera resolver en tiempo polinomial).
Simple: el algoritmo de Euclides permite escribir \(d = mu + nv\) y el número \(x = (bmu+anv)/d\) cumple. En efecto, comprobar que \(x = (amu+bnv)/d \equiv a (m)\) es ver que \(m \mid(bmu+anv)/d -a\) o sea \(dm \mid bmu+anv -ad = bmu + a(nv-d) = bmu-amu = (b-a)mu\), claro simplificando el \(m\) y usando la hipótesis \(d \mid b-a\). La otra es simétrica.