Week 3 - Modular arithmetic and relations

Wednesday, 6 March 2019

10:09 AM

Machine generated alternative text: Multiplication in modular arithmetic looks different to regular multiplication. Here is an example for multiplication in modulo 13. x o 1 2 3 4 5 6 7 8 9 10 11 12 o o o o o 0 o o o o o o 1 o 1 2 3 4 5 6 7 8 9 11 12 2 o 2 4 6 8 10 12 1 3 5 7 11 3 o 3 6 9 12 2 5 8 11 1 4 7 10 4 o 4 8 12 3 7 11 2 6 10 1 5 9 5 o 5 10 2 7 12 4 9 1 6 11 3 8 6 o 6 12 5 11 4 10 3 9 2 8 1 7 7 o 7 1 8 2 9 3 10 4 11 5 12 6 8 o 8 3 11 6 1 9 4 7 2 10 5 9 o 9 5 1 10 6 2 11 7 3 12 8 4 10 o 10 7 4 1 11 8 5 2 12 9 6 3 11 o 11 9 7 5 3 1 12 10 8 6 4 2 12 o 12 11 10 9 8 7 6 5 4 3 2 1 Use this multiplication table to answer following questions. a) The number x such that 3m 1 mod (13) is called the inverse of 3 in Z13. Find the inverse of 3 in Z13. Submit part

 

Machine generated alternative text: b) Solve 3m = 2 c) Solve 3m = 8 1 mod (13). You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered mod (13) for x. Submit part 3 >< (5) = 2 mod (13). You were awarded 1 mark. You scored 1 mark for this part. mod (13) for x. 8 Score: 1/1 Answered Submit part mod (13). You were awarded 1 mark.

 

Machine generated alternative text: d) Solve 9 1 mod (13) forx. Submit part 3 x (6) + 9 = 5 mod (13). You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered

 

Machine generated alternative text: Here is the multiplication table in modulo 9. It's a bit different to the multiplication table for the previous question. x o 1 2 3 4 5 6 7 8 o o o o o 0 o o o 1 o 1 2 3 4 5 6 7 8 2 o 2 4 6 8 1 3 5 7 3 o 3 6 o 3 6 o 3 6 1 4 o 4 8 3 7 2 6 1 5 5 o 5 1 6 2 7 3 8 4 6 o 6 3 o 6 3 o 6 3 7 o 7 5 3 1 8 6 4 2 8 o 8 7 6 5 4 3 2 1 Notice that in row a the numbers are all multiples of gcd(a, 9). a) Use the multiplication table to find a non-zero number a such that ax Hint: look for row a where gcd(a, 9) > 1. mod (9) has no solutions. Submit part 6T 1 mod (9) has no solutions. You were awarded 1 mark. You scored 1 mark for this part.

 

Machine generated alternative text: b) Solve 8x = 7 c) mod (9) form. There are two solutions to 16T 14 mod (18) which are a; 2 and 11 Notice that each part of the equation 16T 14 mod (18) has a common factor of Score: 1/1 Answered Submit part 8 >< (2) = 7 mod (9). You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Submit part Your answer is correct.

 

Machine generated alternative text: This common factor can be removed to obtain an equivalent equation with smaller modulus 8x = 7 mod (9). Your answer to part b is a solution to this equation, let's call it x. In fact all the numbers . 18, x 9, x, x 9, x + 18, are solutions to this equation, and in mod (9) they are all the same. So there is really only one answerin mod (9). But in mod (18) the numbers x and x + 9 are different. So there are two answers in mod (18) which are different by 9. Hide steps (Your score will not be affected.) Submit part You revealed the steps. Gap 1 16 x (2) — 14 mod (18). You were awarded 1 mark. Gap 2 16 x (11) — 14 mod (18). You were awarded 1 mark. You scored 2 marks for this part. Score: 2/2 Answered

 

Machine generated alternative text: The general method for solving an equation of the form ax gcd(a, b) along with the numbers x, y such that a) c (mod b) is called the Extended Euclidean Algorithm, which is procedure forfinding ax + by = gcd(a, b). Remember thata:r mod (b) is always a multiple of the gcd(a, b). So it's possible to tell straight away that there are no solutions to the equation 23772x b) 1 mod (47544), because 1 is not a multiple of Submit part Gap 1 Your answer is correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered The Extended Euclidian Algorithm can be used to solve23772x = 6 (mod 2622) by reducing the problem via modular arithmetic. This isa similar method to the previous question, except this time we keep track of the quotients: 23772 2622 174 12 2622qo + 174 where qo 174m + 12 12,72 + 6 whereql = where q2 Stop when you see a remainder of zero, because this means that the gcd(23772, 2622) = gcd(6, 0) = 6. Treat the numbers as symbols (no simplification) and use back-substitution to eliminate the remainders 12 and 174. The result is an expression of the gcd in the form 23772x + 2622y.

 

6 174 — 12T2 = 174 — (2622 — 174q1)T2 — 174(1 + 2622q2 = (23772 + qiT2) 2622112 = 23772(1 + qua) — 2622(q2 + qo(l + q«n)) substitute 12 = 2622 — 174m collect like terms substitute 174 = 23772 — 2622qo collect like terms Now, using the values of the quotients qo, ql , q2 you computed earlier, this means: 6 = 23772 x 211 — 2622 x 1913. So the solution to 23772:r — 6 (mod 2622) is x Submit part Gap 1 Your answer is correct. You were awarded 1 mark. Gap 2 Your answer is correct. You were awarded 1 mark. Gap 3 Your answer is correct. You were awarded 1 mark. Gap 4 Your answer is correct. You were awarded 1 mark. You scored 4 marks for this part. Score: 4/4 Answered

 

A relation Rfrom set A to set B is a subset of the Cartesian product Ax B— e A,be B}. If (a, b) e Rthen we use the special notation aRb, which means that a is related to b by R- Consider thesetsA = {4, 3, 0} and B = {7, 9, 8, 0}, and the relation a) Which elements are related? 7R7 Z 3R0 b) If ORB then what are the possible values of b? 03 04 Z 0R9 Z OR7 Submit part You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You chose a correct answer. You were awarded 0.25 marks. You scored 1 mark for this part. Score: 1/1 Answered

 

Submit part 'Xin RS. You were awarded 0.5 marks. 'Xin RS. You were awarded 0.5 marks. You scored 1 mark for this part. Score: 1/1 Answered

 

Let A = {0, 1, 2, 3}. A matrix M can be used to define a relation R C A x A as R — Ma,b = 1}. For example, consider the relation R defined by the matrix 1 1 o 1 1 1 o o 1 1 1 o 1 1 1 This relation can be visualised as an arrow diagram using A as the set of vertices, and R as the set of directed edges, where aRb means there is an edge from vertex a to vertex b: If desired, you can drag the verticies to get a better look at the arrows. Match the following matricies with their arraow diagram. 1 1 o o o o o o 1 o o o 1 1 1 o o 1 o 1 o 1 1 o 1 o o 1 1 o o 1 1 1 o 1 o 1 o o o o 1 1 1 1 1 o 1 1 o o 1 1 1 1 o o 1 1 1 o 1 1

 

Machine generated alternative text:

 

One of the most important relations is called equality. We say that a relation — is an equivalence relation when it has the three characteristic qualities of equality: • every value should be equal to itself • ifa = bthenb = a • ifa = band b = cthena = c- Let's explore these properties a) If a relation has the property that every element is related to itself, then it is called reflexive. The adjacency matrix for a reflexive relation has 1 's down the long diagonal, and the adjacency diagram for a reflexive relation has loops at each vertex. Check all adjacency diagrams that are reflexive. Submit part You chose a correct answer. You were awarded 1 mark. You chose a correct answer. You were awarded 1 mark. You scored 2 marks for this part. Score: 2/2 Answered

 

b) If a relation has the property that every relation between elements reciprocated, then it is called symmetric. The matrix for a symmetric relation is symmetric: MT = M. Check all adjacency diagrams which correspond to symmetric relations. Submit part SWar{S1} = You were awarded 1 mark. SWar{S2} = You were awarded 1 mark. You scored 2 marks for this part. Score: 2/2 Answered

 

c) A transitive relation is one with the property that if aRb and bRe then aRe. In terms of the adjacency diagram, this means that for every two connected edges (a, b) and (b, c), the shortcut (a, c) is also an edge in the graph. Check all adjacency diagrams which correspond to transitive relations. Submit part You chose a correct answer. You were awarded 1 mark. You chose a correct answer. You were awarded 1 mark. You scored 2 marks for this part. Score: 2/2 Answered

 

Machine generated alternative text: Consider the set A , 8} and the equivalence relation R which has the following adjacency diagram The equivalence relation partitions the set A into equivalence classes. These are sets of elements which are equal. Untangle the adjacency diagram and you will see there are 4 connected components. Each connected component corresponds to an equivalence class. a) Which elements of A are equivalent to 2? Give your answer using the NUMBAS syntax for set. For example the syntax for {0, 1, 2} is set(Ø, 1, 2) . set (2, 6) Submit part

 

Machine generated alternative text: Your answer is numerically correct. You were awarded 0.5 marks. You scored 0.5 marks forthis part. Score: 0.5/0.5 Answered b) Which elements of A are equivalent to 1? This is also called the equivalence class of 1. set (1, s) Submit part Your answer is numerically correct. You were awarded 0.5 marks. You scored 0.5 marks forthis part. Score: 0.5/0.5 Answered c) What is the equivalence class of 3? set (3, 7 ) Submit part Your answer is numerically correct. You were awarded 0.5 marks. You scored 0.5 marks forthis part. Score: 0.5/0.5 Answered

 

Machine generated alternative text: d) aRb exactly when O a b(mod3). b (mod 4). O a — b(mod 5). Submit part You chose a correct answer. You were awarded 0.5 marks. You scored 0.5 marks for this part. Score: 0.5/0.5 Answered

 

 

Created with Microsoft OneNote 2016.