2

I need to find the value of a mod m. But I don't have the value of a directly. I have the following modulus values of a.
a mod 21
a mod 22
a mod 23
...
a mod 2n

Now I need to find a mod m where m < 2n
Is it possible to do so with this much information?

UPDATE
Or if it is not possible with above set then can we have some set of n numbers for which if we have a modulus to all of them, then we can find a mod m for m < 2n

Shashwat Kumar
  • 322
  • 4
  • 15

1 Answers1

1

If we know $a$ modulo $2^n$, then we know $a$ modulo $2^k$ for all $k\lt n$. So the long list is effectively much shorter than it looks.

Suppose that $m\gt 1$ is odd. Let $a$ be given, and let $b$ be any number with $0\le b\le m-1$. By the Chinese Remainder Theorem, there exists an $x$ such that $x\equiv a\pmod{2^n}$ and $x\equiv b\pmod{m}$.

More informally, given the remainder when $a$ is divided by $2^n$, one knows nothing about about the remainder when $x$ is divided by $m$.

André Nicolas
  • 507,029
  • I got that it is not possible. I have updated the problem. Please see it. – Shashwat Kumar Aug 05 '13 at 04:48
  • @Shashwat: Might as well make the moduli relatively prime. If all prime powers $\lt 2^n$ occur as divisors of one of the $n$ moduli, then we will be OK. Another more important way we may be OK is if calculations only involve addition/subtraction and multiplication, and all intermediate results ("$a$") don't get too huge. Then we can work independently modulo carefully chosen $m_i$, and stitch together the answer at the end using the Chinese Remainder Theorem. – André Nicolas Aug 05 '13 at 04:56
  • So it doesn't seem possible to have about log m numbers, which have all prime powers as divisors and are pairwise coprimes. Am I right? – Shashwat Kumar Aug 05 '13 at 05:03
  • Why not? The numbers may have to be pretty big. There are good estimates (sorry, no immediate reference) for the lcm of the integers up to $N$ (in your case $2^n$). – André Nicolas Aug 05 '13 at 05:10