with
is the greatest common divisor is solvable.
Let one solution to the original equation be . Then the solutions are , , , ..., . If , then there is only one solution .

The solution of a linear congruence can be found in the Wolfram Language using Reduce[a*x
== b, x, Modulus -> m].

Solution to a linear congruence equation is equivalent to finding the value of a fractional congruence, for which a greedy-type algorithm
exists. In particular, (1) can be rewritten as