This question arrised when I was solving a computer science problem. I don't know the value of N, as N may be very large, but instead I know the value of $N \mod m$. Assume N is divisible by 2. How can I compute the value of $N/2 \mod m$?
If N is divisible by 3, how do I compute $N/3 \mod m$ ?
Edit: m is known, is odd.
This depends if you know $2^{-1} \mod m$ , this can be easily computed/verified if it exists if you know $m$, as you are solving
$$ 2*k = m*j + 1$$
for integers $k,j$ which can be done using the Euclidean algorithm (assuming $m$ is odd) just multiply with $N \mod m$ and you are golden. Now if $m$ is even there is still "some" case work you can do, namely $2$ divides $m$ and more importantly you can decide based on $N$ which "factor class" it belongs to of $m$ and using that information you can recover back $\frac{N}{2} \mod m$, but this has limitations,
example if $m$ = 8 and $N \equiv 4 \mod 8$ then we have $N = 8k + 4 \rightarrow \frac{N}{2} = 4k + 2 \rightarrow \frac{N}{2} \equiv 2,6 \mod 8$
Here there isn't a unique solution, but we can still compute all the possible solutions