Resolver ecuaciones de congruencia con módulo desconocido

Question

Necesito resolver el siguiente sistema de congruencias lineales:

$$ m_1 \equiv n_1 x\bmod y \\ m_2 \equiv n_2 x\bmod y \\ m_3 \equiv n_3 x\bmod y $$

donde $x$ y $y$ son desconocidos.

Vi algunas preguntas similares, como Resolución de congruencias lineales con módulo desconocido pero parece que sólo es adecuado en determinadas condiciones. Quiero un algoritmo general para resolver esto. ¿Alguien podría ayudarme?

Answer 1

El sistema

$$ m_1 \equiv n_1 x\bmod y \\ m_2 \equiv n_2 x\bmod y \\ m_3 \equiv n_3 x\bmod y \tag 1 $$

es lo mismo que

$$ m_1 = n_1 x + ay \\ m_2 = n_2 x + by \\ m_3 = n_3 x + cy \tag 2 $$

donde $a,b,c$ son números enteros.

Se trata de un sistema de ecuaciones en 5 variables $a,b,c,x,y$ y con 3 ecuaciones. Por lo tanto, sólo hay familias de soluciones. Por ejemplo. Fijar $a$ tal que $\gcd(n_1,a) | m_1$ . A continuación, puede resolver la primera ecuación $m_1 = n_1 x + ay$ utilizando el algoritmo euclidiano ampliado para obtener un número infinito de soluciones para $(x,y)$ que puede comprobarse en la segunda y tercera ecuaciones de (2) para soluciones integrales $(a,b)$ . Si $a,b$ no son números enteros, puede descartar $x,y$ y comprueba el siguiente.

Tendrás un número infinito de soluciones.