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, 06: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. - Jun 1st 2009, 12:16 AMGamma
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)