I am trying to solve the discrete logarithm using the baby-step giant-step algorithm which requires the computation of $a^{-1}$ by using the set of substitutions to reduce it to a case where $\gcd(a, n) = 1$.
If $\gcd(a,n)=g>1$ then if $g\nmid b$ there's clearly no solution. Otherwise write $a=g\alpha$, $b=g\beta$, $n=g\nu$, so $$ a^x\equiv b\pmod{n} \iff g^{x-1}\alpha^x\equiv \beta \pmod{\nu} $$ Since $\gcd(\alpha,\nu)=1$, $\alpha$ has an inverse mod $\nu$. Divide through by $\alpha$ to get $$(g\alpha)^{x-1} = a^{x-1} \equiv \beta\alpha^{-1} \pmod{\nu}$$ If $\gcd(a,\nu)=1$ then use baby-step giant step on this DLP, otherwise repeat this reduction.
But working through the following example: $2^x \equiv 4 \pmod{8}$. The solution is clearly $2$
Following the set of reductions in Zander's answer
$2^{x-1} \equiv 2 \pmod{4}$ since $\gcd(2, 4) = 2$ which divides $b = 2$ we continue again
$2^{x-2} \equiv 1 \pmod{2}$ but now since $\gcd(2, 2) = 2$ does not divide $b = 1$ so there is no solution.
But there clearly is, where have I gone wrong?
If $g\nmid b$ but $b\equiv1\bmod n,$ there is the solution $x=0.$