Thread: Solving congruences

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:
(mod n)

step 3. Multiply both sides by k to get:
(mod n)