2
$\begingroup$

I've tried searching but I haven't been able to find an answer. There are similar questions about reversing modulo operation here on stackexchange, but I haven't found a question which is applicable to my problem.

All answers I've found on reversing modulo says that you cannot uniquely determine the original answer. (At least if I understand them right.)

But let's say we know that:

$x \!\mod 10 = 13\ $ and $\ x \!\mod 13 = 2$.

Can we with this method uniquely determine $x$ if we have $n$ amount of these equations? I'm guessing that if $n \rightarrow \infty$ we can do it, but would this be the only case?

I hope I'm making sense, thanks!

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Chinese Remainder Theorem $\endgroup$ – Matthew Towers Mar 18 '16 at 22:19
  • $\begingroup$ Well, wouldn't we only be able to determine a solution to modulo $\prod_n m$? $\endgroup$ – fleablood Mar 18 '16 at 22:20
  • $\begingroup$ If you add the product of all modulos to $x$, then that is another solution. $\endgroup$ – Henricus V. Mar 18 '16 at 22:23
0
$\begingroup$

If you have the $n$ equations: $$ x\bmod m_1=m_2 $$ You won't be able to determine $x$ better than $$ \text{lcm}(m_1,m_2,\ldots,m_n) $$ ($\text{lcm}$ meaning "least common multiple").

Search for "Chinese remainder theorem" for more information.

Improve this answer
$\endgroup$

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.