Doing modular division when denominator and modulus not coprime So normally if you calculate $n/d \mod m$, you make sure $d$ and $m$ are coprime and then do $n[d]^{-1}\mod m$ , all $\mod m$. But what if $d$ and $m$ are not coprime? What do you do?
 A: If $\gcd(m,d)=g$ and $g\mid n$, then you can perform the standard modular division on
$$
\left.\frac{n}{g}\middle/\frac{d}{g}\right.\left(\text{mod}\frac{m}{g}\right)\tag{1}
$$
Note that the division reduces the modulus, too.
The original equation
$$
dx\equiv n\pmod{m}\tag{2}
$$
is equivalent to
$$
dx+my=n\tag{3}
$$
To solve $(3)$, we need to divide through by $g$:
$$
\frac{d}{g}x+\frac{m}{g}y=\frac{n}{g}\tag{4}
$$
and $x$ in $(4)$ is given by $(1)$.
For example, suppose we know that
$$
12x\equiv9\pmod{15}
$$
we would solve
$$
4x\equiv3\pmod{5}
$$
and any solution would only be known mod $5$; that is,
$$
x\equiv2\pmod{5}
$$
A: You are trying to solve the congruence $xd\equiv n \pmod{m}$. Let $e$ be he greatest common divisor of $d$ and $m$. Since $e$ divides $d$ and $m$, if the congruence has a solution, $e$ must divide $n$.  If $e$ does not divide $n$, division is not possible.
So let us assume that $e$ divides $n$. Then division is sort of possible, but as we shall see, not entirely satisfactory.  
Let $d=d_1e$, $m=m_1e$, and let $n=n_1e$. Then 
$$xd\equiv n\pmod{m}\quad\text{if and only if}\quad xd_1\equiv n_1\pmod{m_1}.$$
Since $d_1$ and $m_1$ are relatively prime, the congruence on the right has a unique solution modulo $m_1$, found in the usual way.
Call the solution $x_0$. Then the solutions modulo $m$ are $x_0+im_1$, where $i$ ranges from $0$ to $e-1$. Thus modulo $m$ division is possible, but it has several answers.  
