Questions and Answers #2 Congruence

Questions and Answers Sheet 2 Congruence Question #1 The value of the operation [13]6 in 𝑍15 and to write the answer in the form [r] with 0 ≤ 𝑟 < 𝑚 . Answer: Definition used: Congruence. Let m be an integer greater than 1. If xand yare integers, then x is congruent to y modulo m if x - y is divisible by m. It can be represented as 𝑥 = 𝑦(𝑚𝑜𝑑 𝑚). This relation is called as congruence modulo m. Calculation: Consider the values and congruence classes modulo m, [13]6 and m = 15. It is evident that [x]=[y] if [𝑥 = 𝑦(𝑚𝑜𝑑 𝑚)]. Since 13 = −2(𝑚𝑜𝑑 15). Then, [13]=[-2] [13]6 = [−2]6 = [(−2)6 ] = [64] Since, by the principal or congruence 64 = 4(𝑚𝑜𝑑 15) . Therefore, [13]6 = [4] in 𝑍15 . Therefore, the value of the expression is [4]. Question #2 To solve: The system of congruence 𝑥 = 2(𝑚𝑜𝑑 3), 𝑥 = 1(𝑚𝑜𝑑 4), and 𝑥 = 3(𝑚𝑜𝑑 5) using the method of back substitution Answer: Given information: 𝑥 = 2(𝑚𝑜𝑑 3), 𝑥 = 1(𝑚𝑜𝑑 4), and 𝑥 = 3(𝑚𝑜𝑑 5) Calculation: By definition, the first congruence can be written as x = 3t +2 where t is an integer. Substituting this expression for x into the second congruence tells us that 3𝑡 + 2 = 1(𝑚𝑜𝑑 4), which can easily be solved to show that 𝑡 = 1 (mod 4) . From this we can write t = 4u + 1 for some integer u. Thus x= 3t+2 = 3(4𝑢 + 1) + 2 = 12𝑢 + 5. We plug this into the third congruence to obtain 12𝑢 + 5 = 3(𝑚𝑜𝑑 5), which we easily solve to give 𝑢 = 4(𝑚𝑜𝑑 5). Hence u =5v +4, and so 𝑥 = 12𝑢 + 5 = 12(5𝑣 + 4) + 5 = 60𝑣 + 53. We check our answer by confirming that 53 = 2(𝑚𝑜𝑑 3), 53 = 1(𝑚𝑜𝑑 4), and 53 = 3 (mod 5) . Thus, x= 60k +53. This is the solution for the system of congruences for every k that is an integer. Question #3 To prove 𝑎𝑥 2 + 𝑏𝑥 + 𝑐 ≡ 𝑎𝑦 2 + 𝑏𝑦 + 𝑐(𝑚𝑜𝑑 𝑚) if a, b and c are integers and x\equiv y(mod m) . Answer: Formula used: Concept of congruence. x is said to be in congruence with yif x - y is divisible by m. Thus, 𝑥 ≡ 𝑦(mod m) Calculation: Consider that a, b, and care integers also 𝑥 ≡ 𝑦 (mod m) . Since 𝑥 ≡ 𝑦 (mod m), and x - y is divisible by m. Therefore, a(x -y) (x+y) and b (x - y) is divisible by m. Further, 𝑎(𝑥 2 − 𝑦 2 ) and b(x-y) is divisible b m. Further, 𝑎(𝑥 2 − 𝑦 2 ) + 𝑏(𝑥 − 𝑦) + 𝑐 − 𝑐 is divisible by m. [𝑎𝑥 2 + 𝑏𝑥 + 𝑐] − [𝑎𝑦 2 + 𝑏𝑦 + 𝑐] is divisible by m. [𝑎𝑥 2 + 𝑏𝑥 + 𝑐] ≡ [𝑎2 + 𝑏𝑦 + 𝑐](𝑚𝑜𝑑 𝑚) Therefore, it is evident that if 𝑥 ≡ 𝑦(𝑚𝑜𝑑 𝑚) then 𝑎𝑥 2 + 𝑏𝑥 + 𝑐 ≡ 𝑎𝑦 2 + 𝑏𝑦 + 𝑐(𝑚𝑜𝑑 𝑚). Question #4 Find all solutions to the congruence 6𝑥 ≡ 9(𝑚𝑜𝑑 45) Answer: Step 1 To Determine : All solutions to the congruence : 6𝑥 ≡ 9(𝑚𝑜𝑑 45) Step 2 All solutions to the congruence : 6𝑥 ≡ 9(𝑚𝑜𝑑 45) Here , in this question , The general linear congruence is 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑 𝑚) On comparing we get, a=6, b=9, m=45 ∴ 𝑑 = (𝑎, 𝑚) = (6,9) = 3. Now, d(=3) divides b (=45). Thus, the solution of given congruence exists and is unique. Now, 6𝑥 ≡ 9(𝑚𝑜𝑑 45) 2𝑥 ≡ 3(𝑚𝑜𝑑 15) Then, 2x-3=15k 2x=15k+3 right ⇒ 𝑥 = 15𝑘+3 2 Substitute, k = 1 , 3 , 5, we get 15 × 1 + 3 15 + 3 𝑥= = 2 2 18 ⇒𝑥= =9 2 15 × 3 + 3 45 + 3 𝑥= = 2 2 48 ⇒𝑥= = 24 2 15 × 5 + 3 75 + 3 𝑥= = 2 2 78 = 39 2 Hence , All The solutions of the congruence: x=9,24,39 ⇒𝑥= Question #5 To perform: The operation [-12]+[95] in 𝑍25 and indicate the answer in [r] where 0 ≤ 𝑟 ≤ 𝑚. Answer: Procedure used: Procedure to perform operation in 𝑍𝑚 . 1 Consider the operation. 2 Perform the operation with the help of congruence. 3 Obtain and dictate the answer. Viability of congruence. The congruence defined as x = y(mod m) is true if x - y is divisible by m. Calculation: Consider the given operation as below. [-12]+[95] It is evident that [x]+[y]=[x+y]. That is, [-12]+[95] can be further simplified as follows: [-12]+[95]=[-12+95]=[83] Therefore, in 𝑍25 the above operation can be written as shown below: [-12]+[95]=[83] = [8] (∵ 83 ≡ 8(𝑚𝑜𝑑 25)) Therefore, the operation [-12]+[95] in 𝑍25 will result as [-12]+[95]=[8]. Question #6 To perform: The operation [-3][9] in 𝑍15 and indicate the answer in [r] where 0 ≤ 𝑟 ≤ 𝑚 . Answer: Procedure used: Procedure to perform operation in 𝑍𝑚 . 1 Consider the operation. 2 Perform the operation with the help of congruence. 3 Obtain and dictate the answer. Viability of congruence. The congruence defined as x = y(mod m) is true if x - y is divisible by m. Calculation: Consider the given operation [-3] [9]. It is evident that [x][y] = [xy]. [-3][9]=[-3*9]=[-27] Therefore, in 𝑍15 the above operation can be written as shown below: [-3][9] =[-27] = [3] [∵ −27 ≡ 3(𝑚𝑜𝑑 15)] Since 𝑟 = 0 ∈ ([𝑟] where 0 ≤ 𝑟 ≤ 15) . Therefore, the operation [-3][9] in 𝑍15 will result as [-3][9]=[3]. Question #7 State the congruence relation for △ ABC and △ DEF . A. SSS B. SSA C. AAA D. SAS Answer: Step 1 Given, △ ABC and △ DEF We have to write the congruence relation for △ ABC and △ DEF Step 2 In △ ABC and △ DEF AB=DE=4 (Given) AC=DF=3 (Given) BC=EF=4.5 (Given) Then, From SSS(side-side-side) rule of congruence △ 𝐴𝐵𝐶 ≅△ 𝐷𝐸𝐹 So, The correct option is A. Question #8 The value of the operation [11]9 in 𝑍12 and to write the answer in the form [r] with 0 ≤ 𝑟 < 𝑚 . Answer: Definition used: Congruence. Let m be an integer greater than 1. If xand yare integers, then x is congruent to y modulo m if x - y is divisible by m. It can be represented as 𝑥 = 𝑦 𝑚𝑜𝑑 𝑚 . This relation is called as congruence modulo m. Calculation: Consider the values and congruence classes modulo m, [11]9 and m = 12. It is evident that[x]=[y] if [𝑥 = 𝑦 𝑚𝑜𝑑 𝑚 ]. Since 11 = −1 𝑚𝑜𝑑 12 . Then, [11]=[-1] [11]9 = [−1]9 = [−(1)9 ] = [−1] Thus, [11]9 = [−1] in 𝑍11 . Therefore, the value of the expression is [-1]. Question #9 Whether 𝑝 ≡ 𝑞 𝑚𝑜𝑑 𝑚 when p=21, q=53, and m=8. Answer: Definition used: Congruence. Let m be an integer greater than 1. If x and y are integers, then x is congruent to y modulo m if x - y is divisible by m. It can be represented as 𝑥 = 𝑦 𝑚𝑜𝑑 𝑚 . This relation is called as congruence modulo m. Calculation: Given that p = 21,q = 53, and m = 8. For being congruence 21 - 53 = 32 should be divisible by 8. Note that, −32 = −4 ∗ 8 + 0 Here, the remainder is 0. Therefore -32 is divisible by 8. Therefore, When p =21, q=53, and m = 8, 𝑝 ≡ 𝑞 𝑚𝑜𝑑 𝑚 . Question #10 Whether p\equiv q\pmod m when p = 83, q=-23, and m = 6. Answer: Definition used: Congruence. Let m be an integer greater than 1. If xand yare integers, then x is congruent to y modulo m if x - y is divisible by m. It can be represented as 𝑥 = 𝑦 𝑚𝑜𝑑 𝑚 . This relation is called as congruence modulo m. Calculation: Given numbers are p = 83,q = -23, and m = 6. For being congruence 83 + 23 = 106 has to be divisible by 6. Note that, 106 = 17*6 +4. Here, remainder is 4. Therefore, 106 is not divisible by 6. Therefore, when p = 83, q=-23, and m =6, 𝑝 ≡ 𝑞\𝑝𝑚𝑜𝑑 𝑚 . Question #11 To perform: The operation [43]+[32] in 𝑍11 and indicate the answer in [r] where 0 ≤ 𝑟 ≤ 𝑚 . Answer: Procedure used: Procedure to perform operation in 𝑍𝑚 . 1 Consider the operation. 2 Perform the operation with the help of congruence. 3 Obtain and dictate the answer. Viability of congruence. The congruence defined as 𝑥 = 𝑦 𝑚𝑜𝑑 𝑚 is true if x - y is divisible by m. Calculation: Consider the given operation as below. [43] + [32] The above expression can be written as below. [43]+[32]=[43+32]=[75] In 𝑍11 [75] is, [75]=[9] [Because 75 ≡ 9 𝑚𝑜𝑑 11] Therefore, the operation [43]+[32] in 𝑍11 will result [43]+[32]=[9]. Question #12 The value of the operation [11]8 in 𝑍5 and to write the answer in the form [r] with 0 ≤< 𝑚 . Answer: Definition used: Congruence. Let m be an integer greater than 1. If x and y are integers, then x is congruent to y modulo m if x - y is divisible by m. It can be represented as 𝑥 = 𝑦 𝑚𝑜𝑑 𝑚 . This relation is called as congruence modulo m. Calculation: It is known that, [x] = [y] if [𝑥 = 𝑦 𝑚𝑜𝑑 𝑚]. Consider the values and congruence classes modulo m, [11]8 and m = 5. Since 11 = 1 𝑚𝑜𝑑 5 , then [11] = [1] [11]8 = [1]8 = [18 ] = [1] Thus, [11]8 = [1] in 𝑍5 . Therefore, the value of the expression is [1]. Question #13 Find a complete set of mutually incogruent solutions. 7𝑥 ≡ 5 𝑚𝑜𝑑 11 Answer: Step 1 Multiply both sides by 3 in the given congruence equation 7𝑥 ≡ 5 𝑚𝑜𝑑11 and simplify using concept of congruence. 7𝑥 ≡ 5 𝑚𝑜𝑑11 3 ∗ 7𝑥 ≡ 3 ∗ 5 𝑚𝑜𝑑11 21𝑥 ≡ 15 𝑚𝑜𝑑11 −𝑥 ≡ 4 𝑚𝑜𝑑11 Step 2 Now multiply by -1 in the equation −𝑥 ≡ 4 𝑚𝑜𝑑 11 and use the congruence −4 𝑚𝑜𝑑 11 ≡ 7 to find the value of x. −𝑥 ≡ 4 𝑚𝑜𝑑 11 −1(−𝑥) ≡ −4 𝑚𝑜11 𝑥 ≡ 7 𝑚𝑜𝑑 11 Since 𝑥 ≡ 7 𝑚𝑜𝑑 11 means 11 𝑥 − 7 therefore x-7 = 11k where k is an integer. Hence x=7+11k. The set form of the solution is {7 + 11𝑘; 𝑘 ∈ 𝑍}. Question #14 Find a complete set of mutually incogruent solutions. 9𝑥 ≡ 12 𝑚𝑜𝑑 15 Answer: Step 1 Since 15 is not ' number .Prime factorization of 15 is 5 × 3 . Convert the given equation in mod 5 and mod 3. The solution of the equation 9𝑥 ≡ 12 𝑚𝑜𝑑 3 and 9𝑥 ≡ 12 𝑚𝑜𝑑 5 Now solve the above system that will be find out by finding common solution of above equations. Step 2 Solve the equation 9𝑥 ≡ 12 𝑚𝑜𝑑 3 . The equivalent meaning of above equation is 3 9𝑥 − 12 that is 3 3 (3𝑥 − 4) . Since 3 divide 9x-12 always inn-respective of values of 𝑥 ∈ 𝑍 . Therefore solution of equation is 𝑍 . Now solve the equation 9𝑥 ≡ 12 𝑚𝑜𝑑 5 . 9𝑥 ≡ 12 𝑚𝑜𝑑 5 4𝑥 ≡ 2 𝑚𝑜𝑑5 −𝑥 ≡ 2 𝑚𝑜𝑑 5 𝑥 ≡ −2 𝑚𝑜𝑑 5 𝑥 ≡ 3 𝑚𝑜𝑑 5 The solution of the equation x\equiv 3 (mod) 5 is 5k+3 where k is an integer. The common solution of both the equation is 5k+3 where k is an integer. The set form of the solution is {5𝑘 + 3; 𝑘 ∈ 𝑍}. Question #15 To explain: what can be said about the lines 𝑃𝑄 and 𝑅𝑆, it is given that ∠1 ≅ ∠2 and ∠4 ≅ ∠5 . Given: The diagram: Answer: Concept Used: Theorem 2-3: Vertically opposite angles are congruent. Transitive property of congruence: if 𝑎 ≅ 𝑏 and 𝑏 ≅ 𝑐, then 𝑎 ≅ 𝑐 . Theorem 3-5: If two lines are cut by a transversal and alternate interior angles are congruent, then the lines are parallel. Consider the given figure: In this figure, by theorem 2-3, ∠2 ≅ ∠5 (Vertically opposite angles) Also, it is given that, ∠1 ≅ ∠2 and ∠4 ≅ ∠5 Now applying the transitive property of congruence, it can be said that ∠1 ≅ ∠4 From the above figure, it can be observed that the angles ∠1 and ∠4 are the alternate interior angles which are formed when the lines 𝑃𝑄 and 𝑅𝑆 are cut by the transversal 𝑄𝑅 . And since ∠1 ≅ ∠4 , so by the theorem 3-5, it can be said that the lines 𝑃𝑄 and 𝑅𝑆 are parallel. Question #16 To write: The plan to prove ∠1 ≅ ∠2 . Given: The given figure is as follows. Answer: Calculation: By SSS Congruence Theorem, prove that △ 𝑄𝑆𝑉 ≅△ 𝑄𝑇𝑉 . Then, state that ∠𝑄𝑆𝑉 ≅ ∠𝑄𝑇𝑉 . Use the Vertical Angles Theorem, ∠𝑄𝑆𝑉 ≅ ∠1, and ∠𝑄𝑇𝑉 ≅ ∠2. Therefore, by the Transitive Property of Congruence to prove that ∠1 ≅ ∠2 . Question #17 Whether pq ( mod m ) when p = 91, q=37, and m =9. Answer: Definition used: Congruence. Let m be an integer greater than 1. If x and y are integers, then x is congruent to y modulo m if x - y is divisible by m. It can be represented as x= y ( mod m ) . This relation is called as congruence modulo m. Calculation: Given numbers are p = 91,q = 37, and m = 9. For being congruence 91 - 37 = 54 has to be divisible by 9. That is 54 = 6 ∗ 9 + 0. Here, remainder is 0. Therefore, 54 is divisible by 9. Therefore, when p = 91, q = 37, and m = 9, pq ( mod m ) . Question #18 The value of the operation [9]7 in 𝑍7 and to write the answer in the form [r] with 0 ≤ 𝑟 < 𝑚 . Answer: Definition used: Congruence. Let m be an integer greater than 1. If x and y are integers, then x is congruent to y modulo m if x - y is divisible by m. It can be represented as m. Calculation: It is known that, [x] = [y] if [x = y x= y ( mod m ) . This relation is called as congruence modulo ( mod m )] . Consider the values and congruence classes modulo m, [9]7 and m = 7. It is evident that. Since 9=2 ( mod 7 ) . Therefore, [9] = [2] [9]7 = [2]7 = [27 ] = [128] Since 128 = [2] in 𝑍7 . Thus [9]7 = [2] in 𝑍7 . Therefore, the value of the expression is [2]. Question #19 To prove: 𝑈𝑄 ≅ 𝑉𝑄 Given information: 𝑆𝑈 ≅ 𝑆𝑉, ∠1 ≅ ∠2 Answer: Proof: FSP2210403481.jpgFSZ Consider △ 𝑈𝑄𝑆, △ 𝑉𝑄𝑆 𝑆𝑈 ≅ 𝑆𝑉 (Given) ∠1 ≅ ∠2 (Given) 𝑄𝑆 ≅ 𝑆𝑄 (As per reflexive property of congruence, if l is a line segment then 𝑙 ≅ 𝑙 ) So, △ 𝑈𝑄𝑆 ≅△ 𝑉𝑄𝑆 (according to SAS congruence criteria, if two sides and the included angle of one triangle are congruent to the two sides and the included angle of another triangle then the two triangles are said to be congruent) Therefore, 𝑈𝑄 ≅ 𝑉𝑄 (corresponding sides of congruent triangles are congruent) Question #20 The smallest positive integer x that satisfies x3 ( mod 5) x  5 ( mod 7 ) x  7 ( mod1)1 Answer: x3 ( mod 5) x  5 ( mod 7 ) . We know gcd(5,7)=1. Also, 1=(3)5-2(7). Thus, x = 5(3)5 − 3.2(7) = 75 − 42 = 33 ( mod 3) 5 Now, let us find the solution for the congruences given below: x = 33 ( mod 35) x  7 ( mod11) We know gcd(35,11)=1. Also, 1=-5(35)+16(11). Thus, 𝑥 = 7(−5)(35) + 33(16)(11) = −1225 + 5808 = 4583