Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.