Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.)

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.