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?
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.
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
