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 you can use your preferred algorithm for the relatively prime case, otherwise repeat this reduction.
Example 1: $6^x \equiv 4 \pmod{44}$
Using $3\cdot 15 \equiv 1 \pmod{22}$ and $3\cdot 4 \equiv 1 \pmod{11}$: $ \begin{align} 2^{x-1}3^x & \equiv 2 \pmod{22} \\ 6^{x-1} & \equiv 2\cdot 15 \equiv 8 \pmod{22} \\ 2^{x-2}3^{x-1} & \equiv 4 \pmod{11} \\ 6^{x-2} & \equiv 4\cdot4 \equiv 5 \pmod{11} \\ \end{align} $ Now $\gcd(6,11)=1$, so if you can solve this you might get $x-2=6$, $x=8$.
Example 2: $6^x \equiv 2 \pmod{44}$
Starting as in Example 1: $ \begin{align} 2^{x-1}3^x & \equiv 1 \pmod{22} \\ 6^{x-1} & \equiv 2\cdot 15 \equiv 15 \pmod{22} \\ \end{align} $ and this has no solution since $\gcd(6,22) \nmid 15$.