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: