# Given two integers for which I know the modulo given a divisor, what can I know of the modulo of their multiplication?

With all symbols representing integers, I know:

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

And I am now looking for $m_c$ and $d_c$ such that:

$$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$$

In words, given two integers for which I know the modulo given a certain divisor, I'm looking for the largest divisor for which I can also know the modulo of their multiplication.

I've had a hard time trying to tackle this analytically. Trying this on some examples I feel like there's some underlying pattern that can yield me a result which is different from $d_c=1$, but I couldn't manage to put my finger on it. Is there a solution different from 1, and if there is, how can I calculate it?

-

If $g=\gcd(d_a,d_b)$, then you certainly know both $a$ and $b$ modulo $g$, hence you know $c=ab$ modulo $g$ (indeed, $c\equiv m_am_b \pmod g$).
But the answer depends upon $m_a$ and $m_b$ as well. For example, if $m_a=m_b=0$, then you know $ab$ modulo $d_ad_b$.
I think the exact answer is that $$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),$$ but I might have made a mistake. (Outline of proof: first prove the special case when $\gcd(m_a,d_a) = \gcd(m_b,d_b) = 1$; then for the general case, start by dividing all terms in the congruences $a\equiv m_a\pmod {d_a}$ and $b\equiv m_b\pmod {d_b}$ by $\gcd(m_a,d_a)$ and $\gcd(m_b,d_b)$, respectively, and apply the special case.)
Thanks, though I admit I don't understand your proof outline - I'll try to prove this myself using your hints, though, should help. It's also not clear to me how to get $m_c$ from this result. –  Oak Sep 18 '12 at 0:06