How to calculate $(n^{-1})\%(p^a)$ for prime $p$? I actually needed to calculate $(a/b)\%m$ when $m$ is not prime. Here is what I have done so far.
$(a/b)\%m = (a* \text{modinv}(b))\%m$, I can calculate mod inverse only if $m$ and $b$ are co-primes.
So, $m= p_1^{k_1}  p_2^{k_2} \cdots p_n^{k_n}$.
For each prime factor, I will separately calculate $(a/b)\%(p_i^{k_i})$ and then combine all the answers using Chinese Remainder Theorem.
The problem is I am unable to calculate $(a/b)\%(p^k)$, can I please get some help on this.
 A: It looks as if you are trying to solve the congruence $bx\equiv a\pmod{m}$.
If $b$ and $m$ are coprime, use the Extended Euclidean Algorithm to find a $z$ such that $bz\equiv 1\pmod{m}$. Then $az$ is a solution of $bx\equiv a\pmod{m}$, and it is unique modulo $m$.
If $b$ and $m$ are not coprime, then $b$ does not have a modular inverse modulo $m$. However, sometimes we can solve the congruence $bx\equiv a\pmod{m}$.
Let $d=\gcd(b,m)$. If $d$ does not divide $a$, then our congruence does not have a solution.  So suppose that $d$ divides $a$.
Then $b/d$ and $m/d$ are relatively prime. The congruence $(b/d)y\equiv a/d\pmod{(m/d)}$ has a unique solution modulo $m/d$, which we can obtain using the Extended Euclidean Algorithm. 
However, the congruence has $d$ solutions modulo $m$, and from each of these solutions we can obtain a solution of $bx\equiv a\pmod{m}$. 
Informally, if $b$ and $m$ are not relatively prime, then $a/b$ need not exist modulo $m$, and when it exists it is not uniquely defined modulo $m$.
