I understand that to solve ax congruent b modulo n means finding integers c and m such that ax congruent b modulo n is equivalent to x congruent c modulo n.
But.... I don't know how to get there.
goal: solve $\displaystyle ax \equiv b $ (mod n)
Note this has solutions iff $\displaystyle gcd(a,n)=d|b$. This implies $\displaystyle b=kd$.
step 1. Use the Euclidean Algorithm to find integers s and t that satisfy:
$\displaystyle as + nt = d$
step 2. look at this congruence mod n, and notice you get:
$\displaystyle as \equiv d $ (mod n)
step 3. Multiply both sides by k to get:
$\displaystyle a(sk) \equiv dk=b$ (mod n)