Lesson hub

## Can't find the answer? Try online tutoring

We have the UK’s best selection of online tutors, when and for how long you need them.

Getting 1-on-1 support is cheaper than you might think.

### Participating users

Welcome to our free-to-use Q&A hub, where students post questions and get help from other students and tutors.

You can ask your own question or look at similar Maths questions.

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).