I understand that to solveax congruent b modulo nmeans finding integerscandmsuch thatax congruent b modulo n is equivalent to x congruent c modulo n.

But.... I don't know how to get there.

Printable View

- May 31st 2009, 05:22 PMNerdfighterSolving 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 PMGamma
goal: solve $\displaystyle ax \equiv b $ (mod n)

Note this has solutions iff $\displaystyle gcd(a,n)=d|b$. This implies $\displaystyle b=kd$.

step 1. Use the Euclidean Algorithm to find integers s and t that satisfy:

$\displaystyle as + nt = d$

step 2. look at this congruence mod n, and notice you get:

$\displaystyle as \equiv d $ (mod n)

step 3. Multiply both sides by k to get:

$\displaystyle a(sk) \equiv dk=b$ (mod n)