# How to find $a\mod N$ in a specific way?

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$ .

• 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. – Jyrki Lahtonen Nov 12 '14 at 6:19
• How about? $\gcd(a,N,M)$ – Fred Kline Nov 12 '14 at 6:40
• @FredKline can you elaborate ?I am not getting what you are asking ? – john Nov 12 '14 at 7:08
• @JyrkiLahtonen can we solve updated problem . Where M is prime number . – john Nov 13 '14 at 10:54
• 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. – 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.