a divide b mod m when mod inverse doesn't exist I am trying to compute [(2 ^ (2*n-1) + 1) / 3] mod m.  The value for n can be very large, so computations are performed mod m.
The computed value is always an integer, and hence the computation is valid for all m.
When m is not divisible by 3, we can use mod power to compute the power of 2, add 1, then multiply by the mod inverse of 3.
However, I am stuck when m is divisible by 3.  How do we perform the computation when m is divisible by 3?
 A: The point is that $3^{-1}$ is only defined if $\text{gcd}(3,m) = 1$; otherwise you get non-sensical results. In other words 
If $\text{gcd}(3,m) \neq 1$ then division by 3 is the same thing as division by zero (in an abstract sense)
The point is the following:
if \begin{equation}
x y = 1
\end{equation}
and 
\begin{equation}
 y \neq 0  
\end{equation}
 and there exists some 
\begin{equation}
 z \neq 0  
\end{equation}
such that 
\begin{equation}
 yz = 0  
\end{equation} 
then we have that 
\begin{equation}
x y = 1 \implies xyz = z \implies z = 0
\end{equation}
which is a contradiction. 
How does that happen here? Well suppose that there is a $3^{-1} \not\equiv 0 $ mod 6 for example, then
\begin{equation}
3 (3^{-1}) \equiv 1 \ (\text{mod} 6)
\end{equation}
but 
\begin{equation}
 3 \not\equiv 0  \ (\text{mod} 6)
\end{equation}
 and 
\begin{equation}
2 \not\equiv 0  \ (\text{mod} 6)  
\end{equation}
and 
\begin{equation}
2 \cdot 3 \equiv 0  \ (\text{mod} 6)
\end{equation} 
then we have that 
\begin{equation}
3 (3^{-1}) \equiv 1 \ (\text{mod} 6) \implies 2 \cdot 3 \cdot (3^{-1}) \equiv 2 \ (\text{mod} 6)\implies 2 \equiv 0  \ (\text{mod} 6) 
\end{equation}
which is a contradiction. 
A: Hint: $ $ if $\,3\mid a\,$ then $\ \bbox[5px,border:1px solid #c00]{a/3 \bmod m = (a\bmod 3m)/3}\ $ by the mod Distributive Law
