Solving $ax \equiv c \pmod b$ efficiently when $a,b$ are not coprime I know how to compute modular multiplicative inverses for co-prime variables $a$ and $b$, but is there an efficient method for computing variable $x$ where $x &lt; b$ and $a$ and $b$ are not co-prime, given variables $a$, $b$ and $c$, as described by the equation below? 

$ a x \equiv c \mod b $ 

For example, given

$ 154x \equiv 14 \mod 182 $, is there an efficient method for computing all the possibilities of $x$, without pure bruteforce?

Please note that I'm not necessarily asking for a direct solution, just a more optimized one.  

I do not believe that the Extended Euclidean Algorithm will work here, because $a$ and $b$ are not co-prime. 

Edit: 
Follow up question, since the first one had a shortcut:

Could the be computed efficiently as well?

$12260x \equiv 24560 \mod 24755$.

$107$ needs to be one of the computed answers.
Solving $154x \equiv 14 \pmod{182}$ is the same as finding all solutions to
$$ 154x + 182y = 14.$$
In this case, we might think of this as finding all solutions to
$$14(11x + 13y) = 14(1),$$
or rather
$$11x + 13 y = 1.$$
Finally, solving this is the same as solving $11x \equiv 1 \pmod {13}$, which has solution $x \equiv 6 \pmod{13}$.

So we learn that $x \equiv 6 \pmod{13}$ is the solution. Of course, this isn't a single residue class mod $182$. Thinking modulo $182$, we see that the solutions are $x \equiv 6, 6+13,6+26,6+39, \ldots, 6+13*13 \equiv 6, 19, 32, \ldots, 175.$

This approach works generally --- factor out the greatest common divisor, consider the resulting modular problem, and then bring it back up to the original problem.
One way to solve the problem ax ≡ c (mod b) would be to treat it as a problem in finding 0,1 for the linear equation ax0 − bx1 = c where ,,,0,1 ∈ . One way to solve the linear equation would be to use substitution in two ways: first to introduce a new variable and a new equation at each step to create a linear system of equations, and second to turn every non-basic variable in the linear system of equation into a basic variable. The motivation for the use of substitution is to express each original variable (0,1) as a basic variable that is a function of parameter variables (0,1,…) such that for any integer value assigned to the parameter variables would result in the original variables taking on integer values. The computations in the algorithm may be organized using augmented matrices.

I have applied one such algorithm to your example problems in "Solving 154x ≡ 14 (mod 182) and 12260x≡ 24560 (mod 24755) Using Augmented Matrices". It also includes an explanation for the algorithm and an animation of the step-by-step solution to the problems.