Given $x\mod n=a$ and $ x\mod m=b$, (here, $n=1000000007$ while $m$ can be any number less than $n$) is there any meathod to find $b$ in terms of $(n,a,m)$...The answer should not contain $x$. I tried some methods but I wasn't able to remove $x$ from the answer. I searched for it on google but I found no property which can solve this.
Asked
Active
Viewed 79 times
2
-
Only if $m = 1$ or $m = n$. $a + k\cdot n$ can take all values modulo $m$ for $1 < m < n$. – Daniel Fischer Aug 09 '13 at 09:41
-
I find the problem somewhat unclear: If $n,a,m$ are given and because $n$ is prime you can compute $x \equiv a^{-1} \mod n$ and substitute $b \equiv x \mod \equiv (a^{-1} \mod n) \mod m.$ – gammatester Aug 09 '13 at 10:54
-
@gammatester consider example 1000000500 mod 1000000007 = 493 but 493^-1 mod 1000000007 = 632860045 (a^−1 mod n = a^n-2 mod n) which is not equal to x 1000000500 mod 13 =5, but 632860045 mod 13 =12 – aitrom Aug 09 '13 at 13:46