1. (More on the Integers Modulo n) Let us first fix n = 7 in this...
Fantastic news! We've Found the answer you've been seeking!
Question:
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.
Expert Answer:
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
Related Book For
Discrete and Combinatorial Mathematics An Applied Introduction
ISBN: 978-0201726343
5th edition
Authors: Ralph P. Grimaldi
Posted Date:
Students also viewed these mathematics questions
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
The Fall 1995 issue of Investment Digest, a publication of The Variable Annuity Life Insurance Company of Houston, Texas, discusses the importance of portfolio diversification for long-term...
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
Four different processes for baking Oreo cookies are considered for the 2008 season. The cookies produced by each process are evaluated in terms of their overall quality. Since the cookies sometimes...
-
Discuss the power of a corporation president to employ a sales manager and to agree that the manager should be paid a stated amount per year plus a percentage of any increase in the dollar volume of...
-
What is a personal representative?
-
What are the four BSC perspectives?
-
Storage Systems, Inc., sells a wide range of drums, bins, boxes, and other containers that are used in the chemical industry. One of the companys products is a heavy-duty corrosion-resistant metal...
-
Stocks originally purchased for $10/share was sold for $50/share. What was the annual return on the investment, if shares were sold after 15 years?
-
The idealized cross-section of a two-cell thin-walled wing box is shown below with the data in Table 22.7. If the wing box supports a load of 44,500 N acting along web 25, calculate the shear flow...
-
What is the loss function for linear regression-Gradient Descent? How does gradient descent update the estimate, give the general formulae? Given X = [1, 2, 3, 4], and Y = [1.5, 2, 2.5, 5). If we...
-
Describe the accounting for a convertible bond. Can the conversion ever result in the recognition of a gain in the income statement?
-
What is the difference between a spin-off and a split-off? Under what circumstances can either result in the recognition of a gain in the income statement?
-
Employee stock options potentially dilute earnings per share (EPS). What can companies do to offset these dilutive effects and how might this action affect the balance sheet?
-
Analysts attempt to identify transitory items in an income statement. Define transitory items. What is the purpose of identifying transitory items?
-
Explain how we account for a cost that creates an immediate benefit versus a cost that creates a future benefit.
-
ONE require an adjustment (Adjusting Entry AJE) a) Prepaid Insurance b) Salary Expense - c) Interest Payable - d) Service Fees Earned - e) Unearned Revenue - f) Depreciation Expense - 4. Emery...
-
Question 6.10 Current and deferred tax worksheets and tax entries From the hip Ltd?s statement of profit or loss for the year ended 30 June 2007 and extracts from its statements of financial position...
-
For each of the following pairs of statements, use Modus Ponens or Modus Tollens to fill in the blank line so that a valid argument is presented. (a) If Janice has trouble starting her car, then her...
-
Pr(A U B) = Pr(A) + Pr()Pr(B) = Pr(B) + Pr()Pr(A).
-
If G = (V, E) is an undirected graph, a spanning subgraph H of G in which each vertex has degree 1 is called a one-factor (or perfect matching) for G. a) If G has a one-factor, prove that |V| is...
-
Consider the following situations: (a) Assume that you are a partner in a two partner practice with total practice income of 250 000. One of your clients (a private limited company with a turnover of...
-
Discuss the arguments for and against requiring the mandatory rotation of auditors.
-
Now that you have read the IFAC Code and the FRC Ethical Standard do you think that they have been influenced by prior work on auditing theory? Justify a Yes or No answer.
Study smarter with the SolutionInn App