Dados dos enteros de los que conozco el módulo dado un divisor, ¿qué puedo saber del módulo de su multiplicación?

Question

Con todos los símbolos que representan números enteros, lo sé:

$$ a \equiv m_a \bmod d_a \\ b \equiv m_b \bmod d_b $$

Y ahora estoy buscando $m_c$ y $d_c$ tal que:

$$ c = ab \\ c \equiv m_c \bmod d_c \\ \forall d_c', m_c': c \equiv m_c' \bmod d_c' \Rightarrow d_c' \le d_c $$

Es decir, dados dos enteros de los que conozco el módulo dado un determinado divisor, busco el mayor divisor del que puedo conocer también el módulo de su multiplicación.

Me ha costado mucho abordar esto de forma analítica. Intentando esto en algunos ejemplos siento que hay algún patrón subyacente que puede darme un resultado que es diferente de $d_c=1$ pero no he podido dar con la clave. Es ¿hay una solución diferente de 1, y si la hay, cómo puedo calcularla?

Answer 1

Si $g=\gcd(d_a,d_b)$ entonces seguro que conoces a los dos $a$ y $b$ modulo $g$ , de ahí que sepas $c=ab$ modulo $g$ (De hecho, $c\equiv m_am_b \pmod g$ ).

Pero la respuesta depende de $m_a$ y $m_b$ también. Por ejemplo, si $m_a=m_b=0$ Entonces ya sabes $ab$ modulo $d_ad_b$ .

Creo que la respuesta exacta es que $$ d_c = \gcd(m_a,d_a) \gcd(m_b,d_b) \gcd\bigg( \frac{d_a}{\gcd(m_a,d_a)}, \frac{d_b}{\gcd(m_b,d_b)} \bigg), $$ pero puede que me haya equivocado. (Esquema de la prueba: primero demostrar el caso especial cuando $\gcd(m_a,d_a) = \gcd(m_b,d_b) = 1$ ; entonces para el caso general, empezar por dividir todos los términos de las congruencias $a\equiv m_a\pmod {d_a}$ y $b\equiv m_b\pmod {d_b}$ por $\gcd(m_a,d_a)$ y $\gcd(m_b,d_b)$ respectivamente, y aplicar el caso especial).