The "? mod n" relation on Z is transitive. Show that it is also symmetric and reflexive.

Symmetry: Suppose

a ? b mod n.

Then

a = b + kn

for some k, so b =

a

? kn, which means that b ? a mod

kn

Reflexivity: For any a,

a = a + 0 n,

so a ? a mod

b

.