0
$\begingroup$

Say we have a natural number $x_1$ modulo a natural number $m_1$, and another natural $x_2$ modulo a natural $m_2$. I'm looking for a function that combines the values so that we get the result of using the Chinese remainder theorem on the numbers. In other words, I'm looking for a formula that would combine results modulo 3 and modulo 5 into results modulo 15, or modulo $3^2 \cdot 5$ and modulo $5 \cdot 7$ into modulo $3^2 \cdot 5 \cdot 7$. I'm really looking for a general method to find functions devoted to specific moduli.

It's a major bonus if this formula is easy to incorporate into a summation, but that may be a tough order.

$\endgroup$
2
$\begingroup$

Suppose $x \equiv x_1 \mod m_1$ and $x \equiv x_2 \mod m_2$, where $m_1$ and $m_2$ are coprime. Let $y$ be the multiplicative inverse of $m_1$ mod $m_2$, i.e. $m_1 y \equiv 1 \mod m_2$. Then $x \equiv x_1 + (x_2 - x_1) m_1 y \mod m_1 m_2$.

$\endgroup$
1
  • $\begingroup$ Wow, that was simple - I think that is what I'm looking for, so thanks! $\endgroup$ – Matt Groff Sep 1 '16 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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