# congruence

prove that ac ≅ bd (mod n).

Answers
Hi!Definition 1.An equivalence relation ˜ on a set S is a rule or test applicable to pairs of elementsof 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 usualnotion of equality among the set of integers is an example of an equivalence relation. The next definitionyields 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 haveac − 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).
Varsha W.
10 July 2017