How would I check the divisibility of two numbers which are both taken under modulo M?
E.g I have calculated a very large sum modulo M and now I want to check if this sum is evenly divisible by a^b where a and b can be as large as 10^9.