Let's I have an integer a and take it's modulo with M (M is a prime Number) which is b.
i.e. $b = {a\mod M}$
I would like to get $a \mod N$ by doing some operation on operation on b along with M , N ? .
i.e. [$a\mod N$] = [b some operation with N , M]
e.g. a = 20 , M = 23 and N=15 then $b = a\mod M$
so , $b = 20 $
$a\mod N = 5 $.
There is any way to get 5 by doing some operation on b along with M , N ?

Note : Here I used square brackets to represent together $a\mod N$ .

  • $\begingroup$ If $N$ is a factor of $M$, then there's no need to do anything as $b\equiv a\pmod M$ the implies that $b\equiv a\pmod N$ (if you are interested in remainders instead of congruence, you can calculate the remainder of $a$ modulo $N$). But if $N$ is not a factor of $M$, then the operation is not well defined. For example $12, 22 $ and $32$ all have remainder $2$ modulo $10$, but their remainders modulo $7$ are $5,1$ and $4$ respectively, so there cannot be a magic formula for getting all of those starting with only $2$ and $7$ without information about the number you started with. $\endgroup$ – Jyrki Lahtonen Nov 12 '14 at 6:19
  • $\begingroup$ How about? $\gcd(a,N,M)$ $\endgroup$ – Fred Kline Nov 12 '14 at 6:40
  • $\begingroup$ @FredKline can you elaborate ?I am not getting what you are asking ? $\endgroup$ – john Nov 12 '14 at 7:08
  • $\begingroup$ @JyrkiLahtonen can we solve updated problem . Where M is prime number . $\endgroup$ – john Nov 13 '14 at 10:54
  • $\begingroup$ Same problem. In my numerical example let's use $M=11$ instead of $10$. Then $12,23$ and $34$ all leave remainder $=1$ modulo $11$, but their remainders modulo $7$ are $5,2$ and $6$ respectively. It may be the first time you try to describe a function that is not well defined. This is what means. Modular arithmetic is full of pitfalls like this, if you want to switch the modulus (here from $11$ to $7$) in the middle of a calculation. $\endgroup$ – Jyrki Lahtonen Nov 13 '14 at 11:40

If $N>M$, that looks difficult, because $b$ can take $M$ different values, while $a\bmod N$ can take $N$ different ones.

If $N<M$, it looks difficult as well, because any $a=b+kM$ will give the same $b$, while $$a\bmod N=(b + kM)\bmod N=(b + (kM\bmod N))\bmod N$$ can take any value.

| cite | improve this answer | |
  • 1
    $\begingroup$ When I say it looks difficult, I mean it is not possible. $\endgroup$ – Yves Daoust Nov 13 '14 at 12:57

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.