Hi!

Definition 1.An equivalence relation ˜ on a set S is a rule or test applicable to pairs of elements

of S such that

(i) a ∼ a , ∀ a ∈ S (reflexive property)

(ii) a ∼ b ⇒ b ∼ a (symmetric property)

(iii) a ∼ b and b ∼ c ⇒ a ∼ c (transitive property) .

You should think of an equivalence relation as a generalization of the notion of equality. Indeed, the usual

notion of equality among the set of integers is an example of an equivalence relation. The next definition

yields another example of an equivalence relation.

Definition 2. Let a, b, n ∈ Z with n > 0. Then a is congruent to b modulo n;

a ≡ b (mod n)

provided that n divides a − b.

Theorem : If a ≡ b (mod n) and c ≡ d (mod n), then

(i) a + c ≡ b + d (mod n)

(ii) ac ≡ bd (mod n) .

Proof.

(i) By the definition of congruence there are integers s and t such that a−b = sn and c−d = tn. Therefore,

a − b + c − d = sn + tn = n(s + t)

or, adding b + d to both sides of this equation,

a + c = b + d + n(s + t) .

Hence, a + c ≡ b + d (mod n).

(ii) Using the fact that −bc + bc = 0 we have

ac − bd = ac + 0 − bd

= ac + (−bc + bc) − bd

= c(a − b) + b(c − d)

= c(sn) + b(tn)

= n(cs + bt)

and so n | (ac − bd). Hence, ac ≡ bd (mod n).