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 (mod n)
Note this has solutions iff . This implies .
step 1. Use the Euclidean Algorithm to find integers s and t that satisfy:
step 2. look at this congruence mod n, and notice you get:
step 3. Multiply both sides by k to get: