# Solving congruences

• May 31st 2009, 05:22 PM
Nerdfighter
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.
• May 31st 2009, 11:16 PM
Gamma
goal: solve $ax \equiv b$ (mod n)
Note this has solutions iff $gcd(a,n)=d|b$. This implies $b=kd$.

step 1. Use the Euclidean Algorithm to find integers s and t that satisfy:
$as + nt = d$

step 2. look at this congruence mod n, and notice you get:
$as \equiv d$ (mod n)

step 3. Multiply both sides by k to get:
$a(sk) \equiv dk=b$ (mod n)