prove that a c mod n iff a cSolutionAssume a c mod n Let b

prove that a c (mod n) iff [a] = [c]

Solution

Assume a c (mod n). Let b [a]_n. Then by definition b a (mod n).

By the transitivity property of congruence we then have a b (mod n) and a c (mod n) b c (mod n) .

So b [c]_n. Thus, any element b of [a]_n is also an element of [c]_n. Reversing the roles of a and c in the argument above we similarly conclude that any element of [c]_n is also an element of [a]_n. Therefore [a]_n = [c]_n .

Conversely, suppose [a] = [c]. Since a a (mod n), by the reflexive property of congruence, we have a [a] and so, since by hypothesis [a] = [c], a [c].

Hence, a c (mod n) .