2

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!

Τίμων
  • 1,669
Tergo
  • 23

1 Answers1

0

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.

Henrik supports the community
  • 6,831