2
$\begingroup$

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?

1 Answers 1

2

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

  • 0
    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.2012-09-18