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 < 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.
Best Answer
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.