1. (More on the Integers Modulo n) Let us first fix n = 7 in this...

Transcribed Image Text:

1. (More on the Integers Modulo n) Let us first fix n = 7 in this question. Everything below is still true for any integer n ≥ 2. Let R be the relation on Z defined by R = {(a,b) € Z x Z : a = b (mod 7)}. We have proved in Example 4.10 that R is an equivalence relation on Z. Moreover, The- orem 4.17 implies that for any a, b € Z, we have [a] = [b] if and only if a = b (mod 7). Recall that Z7 is by definition the set {[0], [1],... [6]} of distinct equivalence classes with respect to the relation R. This is a set of seven elements. We would like to define addition and multiplication on Z7 as follows: [a] + [b] = a + b] and [a] [b] = [ab]. For example, [1] + [3] [4] and [2] [3] [6]. Now, [4] + [5] should be [9] according to the definition, but apparently we do not see [9] among the elements in Z7. However, [9]= [2] as 9 = 2 (mod 7), hence we have [4] + [5] = [2]. (a) Complete the following addition and multiplication tables for Z7: +[0][1] [2] [3] [4] [5] [6] [0] [1] [3] [4] [5] [6] [0] [1] 1 [5] [6] 0 1 2 3 [4] 5] [6] (b) Students A and B were asked to find [25] + [-9] in Z7. Student A's answer: [25] + [-9] = [25+ (-9)] = [16]. Student B's answer: Since [25]= [4] and [-9] = [5] in Z7, so we have [25] + [9] = [4] + [5] = [2]. Luckily, the two answers are the same as [16] = [2] in Z7. But is it just a coincidence? Will this happen every time? Let us try to carry out another calculation: take [3] and [4] in Z7. (i) Find [3] + [4] and [3] . [4]. (ii) We know that [3] = [10] and [4] = [18] in Z7. Find [10] + [18] and [10]. [18]. What do you observe? (c) Now you are asked to show that the above definition of the sum and product of two equivalence classes [2] and [y] does NOT depend on the choice of representatives and y of these classes. More precisely, prove that if [a] = [b] and [c]= [d], then [a+c] = [b+d] and [ac] =[bd]. Remark: This shows that the sum and the product are well-defined. The same situation applies to Z₁, for all n ≥ 2. 2. Let R be a relation defined on Z by aRb if |a| = |b|. It is given that R is an equivalence relation on Z (make sure you know the proof). (a) Find [0] and the equivalence class [a] for any nonzero a € Z. (b) Let E = {[a]: a € Z} be the set of all equivalence classes with respect to R. Define addition and multipli- cation on E by [a] + [b][a + b] and [a] [b] = [ab]. Are these two operations well-defined? Give a proof if you think the operation is well-defined, and give a counterexample if you think it is not. 3. Recall that a function f from a set A to a set B is a relation from A to B that assigns to each element of A a unique element of B. This can be reformulated as the following: A function f from a set A to a set B is a relation from A to B such that (i) the domain of f is the entire set A, and (ii) for any z, y € A, if x =y, then f(x) = f(y). Use this reformulation to prove or disprove that each of the following is a function: (a) f is a relation from Z5 to Z5 defined by f([x]) = [2r +3]. (b) ƒ is a relation from Z3 to Z, defined by f(2)3) = []6, where [2]3 and [2] denote the equivalence classes with respect to the congruence of integers modulo 3 and modulo 6 respectively. If f is a function, determine whether it is bijective. 1. (More on the Integers Modulo n) Let us first fix n = 7 in this question. Everything below is still true for any integer n ≥ 2. Let R be the relation on Z defined by R = {(a,b) € Z x Z : a = b (mod 7)}. We have proved in Example 4.10 that R is an equivalence relation on Z. Moreover, The- orem 4.17 implies that for any a, b € Z, we have [a] = [b] if and only if a = b (mod 7). Recall that Z7 is by definition the set {[0], [1],... [6]} of distinct equivalence classes with respect to the relation R. This is a set of seven elements. We would like to define addition and multiplication on Z7 as follows: [a] + [b] = a + b] and [a] [b] = [ab]. For example, [1] + [3] [4] and [2] [3] [6]. Now, [4] + [5] should be [9] according to the definition, but apparently we do not see [9] among the elements in Z7. However, [9]= [2] as 9 = 2 (mod 7), hence we have [4] + [5] = [2]. (a) Complete the following addition and multiplication tables for Z7: +[0][1] [2] [3] [4] [5] [6] [0] [1] [3] [4] [5] [6] [0] [1] 1 [5] [6] 0 1 2 3 [4] 5] [6] (b) Students A and B were asked to find [25] + [-9] in Z7. Student A's answer: [25] + [-9] = [25+ (-9)] = [16]. Student B's answer: Since [25]= [4] and [-9] = [5] in Z7, so we have [25] + [9] = [4] + [5] = [2]. Luckily, the two answers are the same as [16] = [2] in Z7. But is it just a coincidence? Will this happen every time? Let us try to carry out another calculation: take [3] and [4] in Z7. (i) Find [3] + [4] and [3] . [4]. (ii) We know that [3] = [10] and [4] = [18] in Z7. Find [10] + [18] and [10]. [18]. What do you observe? (c) Now you are asked to show that the above definition of the sum and product of two equivalence classes [2] and [y] does NOT depend on the choice of representatives and y of these classes. More precisely, prove that if [a] = [b] and [c]= [d], then [a+c] = [b+d] and [ac] =[bd]. Remark: This shows that the sum and the product are well-defined. The same situation applies to Z₁, for all n ≥ 2. 2. Let R be a relation defined on Z by aRb if |a| = |b|. It is given that R is an equivalence relation on Z (make sure you know the proof). (a) Find [0] and the equivalence class [a] for any nonzero a € Z. (b) Let E = {[a]: a € Z} be the set of all equivalence classes with respect to R. Define addition and multipli- cation on E by [a] + [b][a + b] and [a] [b] = [ab]. Are these two operations well-defined? Give a proof if you think the operation is well-defined, and give a counterexample if you think it is not. 3. Recall that a function f from a set A to a set B is a relation from A to B that assigns to each element of A a unique element of B. This can be reformulated as the following: A function f from a set A to a set B is a relation from A to B such that (i) the domain of f is the entire set A, and (ii) for any z, y € A, if x =y, then f(x) = f(y). Use this reformulation to prove or disprove that each of the following is a function: (a) f is a relation from Z5 to Z5 defined by f([x]) = [2r +3]. (b) ƒ is a relation from Z3 to Z, defined by f(2)3) = []6, where [2]3 and [2] denote the equivalence classes with respect to the congruence of integers modulo 3 and modulo 6 respectively. If f is a function, determine whether it is bijective.

Answer rating: 100% (QA)

Lets address each part of the problem step by step 1 More on the Integers Modulo a Completing the Addition and Multiplication Tables for Z7 textAdditi... View the full answer