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)