ax is congruent b mod n if and only if d|b, d = gcd(a,n)

[twisted_logic89]

theorem: ax is congruent to b mod n
if and only if
d|b (d = gcd (a,n))

proof:

n | ax - b

a= rd
n= sd

so we could say that sd| (rd)x - b

then....divide everything by d, since d doesnt equal zero cuz its the gcd

so now s|rx-b

am I even on the right track here?

 

[daon]

Let d = gcd(a,n)

Then d|a and d|n.

If n | (ax-b), then d|(ax-b) (divisibility is a transitive relationship).

Have you done a theorem: If a|b and a|(b+c) then a|c? If not, its an easy proof. Using this,

Since d|ax and d|(ax-b), d|b.