Congruences ax = b mod n

[captaincloss]

Hello everyone,

I have a problem. How to solve ax = b mod n, when GCD(a,n) != 1.
Example is:
12x=6(mod 78)
GCD is 3.
Result x is 7, I used this site to check the result: http://www.math.sc.edu/~sumner/numbertheory/rsa/congsolver.html

Can someone please show me step by step how to get that x?

 

[royhaas]

Start by dividing everything through by the GCD.