By the Qutient-Remainder Theorem.docVIP

Summary of Week 10 Lectures 3 and 4 In the previous lecture, we introduced the basic concepts of congruence arithmetic: Definition 1: Let n ( ( and d ( (. We define n div d = the integer quotient obtained when n is divided by d. n mod d = the integer remainder obtained when n is divided by d. Definition 2: Let n????. We will define a relation on ? called congruence modulo n (denoted () by (a, b???? ( a ( b(mod n) ( n | (a - b) ). a ( b(mod n) reads “a is congruent to b modulo n”. a ( b(mod n) if and only if n divides the difference between a and b. a ( b(mod n) if and only if a mod n = b mod n, that is, if a and b have the same remainder after being divided by n. Arithmetic of Congruences Lemma 1: Let n????, and a, b, c, d????. (i) If a ( b(mod n) and c ( d(mod n), then (a + c) ( (b + d)(mod n) and ab ( cd(mod n). (ii) If gcd(a, n) = 1 and ab ( cd(mod n), then b ( c(mod n). Equivalence Classes of Congruence Modulo n Lemma 2: Let n????. If x????, then x is congruent (modulo n) to exactly one element in { 0, 1, 2, …, n – 1 }. Proof: By the Quotient-Remainder Theorem: If x and n 0 are both integers, then there exist unique integers q and r such that x = nq + r and 0 ( r n. Therefore, x ( r(mod n), and the result follows. This lemma is important as it allows us to group integers according to their remainder after dividing by a given number n????. Definition 3: Let n????. We will define the equivalence class determined by s????, denoted [s], by [s] = { x???? | x ( s(mod n) }. Examples 1. The equivalence classes of congruence modulo 4 are [0] = { …, -12, -8, -4, 0, 4, 8, 12, … } [1] = { …, -11, -7, -3, 1, 5, 9, 13, … } [2] = { …, -10, -6, -2, 2, 6, 10, 14, … } [3] = { …, -9, -5, -1, 3, 7, 11, 15, … } [4] = { …, -8, -4, 0, 4, 8, 12, 16, … } = [0] [5] = { …, -7, -3, 1, 5, 9, 13, 17, … } = [1] 2. There are clearly only four distinct (i.e. different) equivalence classes (mod 4): [0], [1], [2], and [3]. Lemma 3: If n????, then there are exactly n distinc