Questions and Answers #1 Congruence

Questions and Answers Sheet 1 Congruence Question #1 If a =-b (mod m) and c =- d(mod m), prove that ac =- bd (mod m) Answer: Proof: 𝑎 = 𝑏 + 𝑞𝑚 𝑐 = 𝑑 + 𝑟𝑚 , some r,q 𝑎𝑐 − 𝑑𝑏 = (𝑏 + 𝑞𝑚)(𝑑 + 𝑟𝑚) − 𝑏𝑑 = 𝑏𝑑 + 𝑏𝑟𝑚 + 𝑞𝑚𝑑 + 𝑎𝑟𝑚2 − 𝑏𝑑 𝑚(𝑏𝑟 + 𝑞𝑑 + 𝑞𝑟𝑚) Divisible by m, so 𝑎𝑐 ≡ 𝑏𝑑 (mod m) Question #2 Solve the system of congruence's 𝑥 ≡ 1(𝑚𝑜𝑑3), 𝑥 ≡ 4(𝑚𝑜𝑑5), 𝑥 ≡ 6(𝑚𝑜𝑑7) Answer: Step 1 Systems of linear congruences may be solved using methods from linear algebra: Matrix inversion, Cramer's rule. In case the modulus is ', everything we know from linear algebra goes over to systems of linear congruences Step 2 Consider the system of congruence 𝑥 ≡ 1(𝑚𝑜𝑑3) 𝑥 ≡ 4(𝑚𝑜𝑑5) 𝑥 ≡ 6(𝑚𝑜𝑑7) Try a solution of the form 𝑥 =3∗5∗𝑎+3∗7∗𝑏+5∗7∗𝑐 Taking the remainders mod 3 , 5 , and 7. It gives the three equations 1 ≡ 35𝑐 ≡ 2𝑐 ≡ −𝑐(𝑚𝑜𝑑3) 4 ≡ 21𝑏 ≡ 𝑏(𝑚𝑜𝑑5) 6 ≡ 15𝑎 ≡ 𝑎(𝑚𝑜𝑑7) ⇒ 𝑎 = 6, 𝑏 = 4, 𝑐 = −1 One solution is therefore 𝑥 = 3 ∗ 5 ∗ 6 + 3 ∗ 7 ∗ 4 + 5 ∗ 7 ∗ (−1) = 139(𝑚𝑜𝑑105) = 34 Question #3 To solve: The congruence 5 + 𝑥 ≡ 2(𝑚𝑜𝑑6) Answer: To solve the congruence 5 + 𝑥 ≡ 2(𝑚𝑜𝑑6) , try each of the numbers 0, 1,2,3,4, and 5 to see which one solves the congruence. For x=0 5 + 0 ≡ 2(𝑚𝑜𝑑 6) , but this is not true since 5 + 0 ≡ 5(𝑚𝑜𝑑 6). So, x = 0 is not the solution of the given congruence. For x=1 5 + 1 ≡ 2(𝑚𝑜𝑑 6), but this is not true since 5 + 1 ≡ 0(𝑚𝑜𝑑 6). So, x= 1 is not the solution of the given congruence. For x =2 5 + 2 ≡ 2(𝑚𝑜𝑑 6), but this is not true since 5 + 2 ≡ 1(𝑚𝑜𝑑 6). So, x = 2 is not the solution of the given congruence. For x=3 5 + 3 ≡ 2(𝑚𝑜𝑑 6) ⇒ 8 ≡ 2(𝑚𝑜𝑑 6) , and it is true. So, x = 3 is the solution of the given congruence. For x=4 5 + 4 ≡ 2(𝑚𝑜𝑑 6) ⇒ 9 ≡ 2(𝑚𝑜𝑑 6) , but this is not true since 9 ≡ 3(𝑚𝑜𝑑 6) . So, x =4 is not the solution of the given congruence. For x=5 5 + 5 ≡ 2(𝑚𝑜𝑑 6) ⇒ 10 ≡ 2(𝑚𝑜𝑑 6) , but this is not true since 10 ≡ 4(𝑚𝑜𝑑 6). So, x = 5 is not the solution of the given congruence. Thus, x = 3 is the solution of the given congruence 5 + 𝑥 ≡ 2(𝑚𝑜𝑑 6) . Final Statement: Therefore, the solution of the congruence 5 = 𝑥 ≡ 2(𝑚𝑜𝑑 6) is x=3. Question #4 Proof that if a ≡ 𝑏(𝑚𝑜𝑑 𝑛) , then 𝑎 + 𝑐 ≡ 𝑏 + 𝑐(𝑚𝑜𝑑 𝑛) and 𝑎𝑐 ≡ 𝑏𝑐 (mod n) . Answer: Step 1 Apply the definition of congruence and divisibility, to express 𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑛). From the definition of congruence, 𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑛) means that 𝑛|(𝑎 − 𝑏) . By the definition of divisibility, n|(a-b) implies that (a-b) is a multiple of n. That is, a-b=nk, where k is an integer. Step 2 To prove 𝑎 + 𝑐 ≡ 𝑏 + 𝑐(𝑚𝑜𝑑 𝑛), add and subtract c on the left hand side of the equation a-b=nk and use the definition of congruence. a-b=nk a-b+c-c=nk (a+c)-(b+c)=nk Since, (a+c)-(b+c) is a multiple of n, implies that 𝑛|[(𝑎 + 𝑐) − (𝑏 + 𝑐)] . Hence, by the definition of congruence, 𝑎 + 𝑐 =≡ 𝑏 + 𝑐(𝑚𝑜𝑑 𝑛) . Thus, if 𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑛) then 𝑎 + 𝑐 =≡ 𝑏 + 𝑐(𝑚𝑜𝑑 𝑛). Step 3 To prove 𝑎𝑐 ≡ 𝑏𝑐(𝑚𝑜𝑑 𝑛), use the definition of congruence and the properties of divisibility. 𝑎 ≡ 𝑏(mod n) implies that n|(a-b) . By the properties of divisibility, if n divides (a-b) then n also divides the multiple of (a-b). That is, n|(a-b)c=n|(ac-bc) Hence, by the definition of congruence, 𝑎𝑐 ≡ 𝑏𝑐( 𝑚𝑜𝑑 𝑛). Therefore, if a\equiv b(mod n) then 𝑎𝑐 ≡ 𝑏𝑐(𝑚𝑜𝑑 𝑛) . Question #5 How can an inverse of a modulo m be used to solve the congruence 𝑎𝑥 ≡ 𝑏(mod m) when gcd(a,m)=1. Answer: Given information: 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑 𝑚) Calculation: In order to solve the congruence, we need an inverse of a modulo m. Here, gcd (a, m) = 1 that means greatest common factor of a and m is 1. So, aand mare ' numbers then an inverse of a modulo m exists. Once we have an inverse 𝑎 of a modulo m, we can solve the congruence ax ≡ 𝑏(𝑚𝑜𝑑 𝑚) by multiplying both sides of the linear congruence by a. Question #6 Solve the linear congruence 7𝑥 = 13(𝑚𝑜𝑑 19) Answer: Given information: 7𝑥 = 13(𝑚𝑜𝑑19) Calculation: Since, 7𝑥 = 13(𝑚𝑜𝑑19) In order to find an inverse of a modulo m, we look for a multiple of a that exceeds multiple of mby 1. 11.7 = 1(𝑚𝑜𝑑 19) So, 11 is the inverse of 7 modulo 19. Multiplying both sides by 11 shows that 11.7𝑥 = 11.13(𝑚𝑜𝑑 19) So, 77 = 1(𝑚𝑜𝑑19) and 143 = 77(𝑚𝑜𝑑 19) Conclusion: The linear congruence of 7𝑥 = 13(𝑚𝑜𝑑 19) is 71 = 1 ( mod 19) and 143 = 77 (mod 19) . Question #7 To solve: The congruence 3𝑥 ≡ 5(𝑚𝑜𝑑 7) Answer: To solve the congruence 3𝑥 ≡ 5(𝑚𝑜𝑑 7) , try each of the numbers 0, 1, 2,3, 4, 5 and 6 to see which one solves the congruence. For x=0 3 × 0 ≡ 5(𝑚𝑜𝑑 7), but it is not true since 3 × 0 ≡ 0(𝑚𝑜𝑑7) . So, x = 0 is not the solution of the given congruence. For x=1 3 × 1 = 5(𝑚𝑜𝑑7). ⇒ 3 ≡ 5(𝑚𝑜𝑑 7) , butit is not true since 3 ≡ 3(𝑚𝑜𝑑 7) . So, x = 1 is not the solution of the given congruence. For x=2 3 × 2 ≡ 5(𝑚𝑜𝑑 7). ⇒ 6 ≡ 5(𝑚𝑜𝑑 7) , but it is not true since 6 ≡ 6(𝑚𝑜𝑑7) . So, x = 2 is not the solution of the given congruence. For x =3 3 × 3 ≡ 5(𝑚𝑜𝑑 7). ⇒ 9 ≡ 5(𝑚𝑜𝑑 7) , but it is not true since 9 \equiv 2 (mod 7) . So, x = 3 is not the solution of the given congruence. For x=4 3 × 4 ≡ 5(𝑚𝑜𝑑 7). ⇒ 12 ≡ 5(𝑚𝑜𝑑 7), and itis true. So, x = 4 is the solution of the given congruence. Thus, x = 4 is the solution of the given congruence 3𝑥 ≡ 5(𝑚𝑜𝑑 7) Final Statement: Therefore, the solution of the congruence 3𝑥 ≡ 5(𝑚𝑜𝑑 7) is x=4 . Question #8 To solve: The congruence 2 − 𝑥 ≡ 8(𝑚𝑜𝑑 9) Answer: To solve the congruence 2 − 𝑥 ≡ 8(𝑚𝑜𝑑 9) , try each of the numbers 0, 1,2,3,4,5, 6,7, and 8 to see which one solves the congruence. For x=0 2 − 0 ≡ 8(𝑚𝑜𝑑 9), but it is not true since 2 − 0 ≡ 2(𝑚𝑜𝑑 9). So, x = 0 is not the solution of the given congruence. For x=1 2 − 1 ≡ 8(𝑚𝑜𝑑 9) , but it is not true since 2 − 1 ≡ 1(𝑚𝑜𝑑 9) . So, x= 1 is not the solution of the given congruence. For x=2 2 − 2 ≡ 8(𝑚𝑜𝑑 9), but is not true since 2 − 2 ≡ 0 (𝑚𝑜𝑑 9) . So, x = 2 is not the solution of the given congruence. For x =3 2 − 3 ≡ 8(𝑚𝑜𝑑 9), and it is true since −1 ≡ 8(𝑚𝑜𝑑 9) . So, x = 3 is the solution of the given congruence. Thus, x = 3s the solution of the given congruence 2 − 𝑥 ≡ 8(𝑚𝑜𝑑 9) Final Statement: Therefore, the solution of the congruence 2 − 𝑥 ≡ 8(𝑚𝑜𝑑 9) is x = 3. Question #9 Solve the following linear congruence, 25𝑥 ≡ 15(𝑚𝑜𝑑 29) Answer: Step 1 The given linear congruence equation is 25𝑥 ≡ 15 (mod 29) Here, a=25, b=15, m=29, And, 𝑔𝑐𝑑(𝑎, 𝑚) = 𝑔𝑐𝑑(25,29) = 1 Hence the congruence has 1 incongruent solution which is given by solving the corresponding Diophantine equation 𝑎𝑥 + 𝑏𝑦 = 𝑚 ⇒ 25𝑥 + 15𝑦 = 29 Step 2 Let us check the value of x=11. That is, at x =11, 11 × 25 + 15 = 275 + 15 = 290 which is 0 mod 29. Hence x=11 is the solution of given equation. Question #10 To find: The smallest positive integer that solves the congruences 𝑥 ≡ 3(𝑚𝑜𝑑 7), 𝑥 ≡ 4(𝑚𝑜𝑑 5) Answer: Given information: The congruences 𝑥 ≡ 3 (mod 7), 𝑥 ≡ 4 (mod 5) Consider the given congruences 𝑥 ≡ 3(𝑚𝑜𝑑 7), 𝑥 ≡ 4(𝑚𝑜𝑑 5) ‘The congruence 𝑥 ≡ 3(𝑚𝑜𝑑 7) means if x is divided by 7, the remainder is 3. So the number x is one of the numbers in the following list: 3, 10, 17, 24, 31, 38, 45, Similarly, the congruence 𝑥 ≡ 4 (mod 5) means if x is divided by 5, the remainder is 4. So the number x is one of the numbers in the following list: 4,9, 14, 19,24, 29,34, 39, 44, The smallest number that is found in both the lists is 24, so the smallest number that solves the congruences 𝑥 ≡ 3(𝑚𝑜𝑑 7), 𝑥 ≡ 4(𝑚𝑜𝑑 5) 𝑖𝑠 24. ⇒ 𝑥 = 24 Final Statement: The smallest positive integer that solves the congruences 𝑥 ≡ 3(𝑚𝑜𝑑 7), 𝑥 ≡ 4(𝑚𝑜𝑑 5)𝑖𝑠𝑥 = 24. Question #11 Solve the linear congruence 7𝑥 + 3𝑦 ≡ 10(𝑚𝑜𝑑 16) . Answer: Step 1 Consider the linear congruence 7𝑥 + 3𝑦 ≡ 10(𝑚𝑜𝑑16). Since gcd (7, 3) = 1 we know at least one solution exists. However, the difference between a linear congruence in one variable and a linear congruence in two variables becomes clear when we see that the congruence 7𝑥 + 3𝑦 ≡ 10(𝑚𝑜𝑑16) has multiple solutions. The existence of one solution comes to fruition upon converting the aforementioned linear congruence to the form 7𝑥 ≡ 10 − 3𝑦 𝑚𝑜𝑑 16 and setting 𝑦 ≡ 0 𝑚𝑜𝑑 16 . This leads us to the linear congruence 7𝑥 ≡ 10 𝑚𝑜𝑑 16 . After multiplying both sides of our congruence by 7, we find 𝑥 ≡ 6 𝑚𝑜𝑑 16 . Therefore, one solution to the linear congruence 7𝑥 + 3𝑦 ≡ 10(𝑚𝑜𝑑 16) is given by 𝑥 ≡ 6 𝑚𝑜𝑑 16 𝑦 ≡ 0 𝑚𝑜𝑑 16 Step 2 Our difference maker comes into play when we let 𝑦 ≡ 1𝑚𝑜𝑑 16 . This gives rise to the congruence 7𝑥 ≡ 7 𝑚𝑜𝑑 16 . In this case we have 𝑥 ≡ 1 𝑚𝑜𝑑 16 . As a result, we find another solution of 7𝑥 + 3𝑦 ≡ 10 𝑚𝑜𝑑 16 is 𝑥 ≡ 1 𝑚𝑜𝑑 16 𝑦 ≡ 1 𝑚𝑜𝑑 16 Question #12 Prove directly from the definition of congruence modulo n that if a,c, and n are integers,n >1, and 𝑎 ≡ 𝑐(𝑚𝑜𝑑 𝑛) , then 𝑎3 ≡ 𝑐 3 (𝑚𝑜𝑑 𝑛). Answer: Step 1 Let a, c and n be integers such that n>1. We have to prove that if 𝑎 ≡ 𝑐(𝑚𝑜𝑑 𝑛) , then 𝑎3 ≡ 𝑐 3 (𝑚𝑜𝑑 𝑛) using the definition of congruence modulo n. Note that, 𝑝 ≡ 𝑞(𝑚𝑜𝑑 𝑛) means n|(p-q) where p and q are integers. So, by the definition of congruence modulo n, 𝑎 ≡ 𝑐(𝑚𝑜𝑑 𝑛) implies that n|(a-c). if n divides (a-c), then n divides any integer multiple of (a-c). Step 2 Since a and c are integers, 𝑎2 + 𝑎𝑐 + 𝑐 2 is also an integer. Now, n divides any integer multiple of (a-c) implies that n divides (𝑎 − 𝑐)(𝑎2 + 𝑎𝑐 + 𝑐 2 ). But, by the algebraic identity (𝑎 − 𝑐)(𝑎2 + 𝑎𝑐 + 𝑐 2 ) = 𝑎3 − 𝑐 3 . So, we can say that n divides (𝑎3 − 𝑐 3 ) and thus n | (a − c ) . 3 3 Therefore, by the definition of congruence modulo n, 𝑎3 ≡ 𝑐 3 (𝑚𝑜𝑑 𝑛) . Question #13 To prove: The system of congruences 𝑥 ≡ 2(𝑚𝑜𝑑 16) and 𝑥 ≡ 3(𝑚𝑜𝑑 9) has no solution. Answer: Given: The system of following congruences: 𝑥 ≡ 2(𝑚𝑜𝑑 6) … (1) 𝑥 ≡ 3(𝑚𝑜𝑑 9) … (2) Formula used: The congruence: 𝑎 ≡ 𝑏(𝑚𝑜𝑑 𝑚), iff 𝑎 = 𝑘𝑚 + 𝑏 Proof: Consider the system of following congruences: 𝑥 ≡ 2(𝑚𝑜𝑑 6) … (1) 𝑥 ≡ 3(𝑚𝑜𝑑 9) … (2) The equations (1) and (2) implies that x=6p+2 and x=9q+3 Let us consider x=9q+3 =3(3q+1) Here, x is divisible by 3. Now, consider 𝑥 = 6𝑝 + 2 = 2(3𝑝 + 1) Here, x is divisible by 2 but not by 3. Thus, it is proved that the system of congruences 𝑥 ≡ 2(𝑚𝑜𝑑 6) and 𝑥 ≡ 3(𝑚𝑜𝑑 9) has no solution. Question #14 To find: A positive for the congruence 210𝑥 = 8(𝑚𝑜𝑑 13) . Answer: Given information: 210 × 7 = 1(𝑚𝑜𝑑 13) Concept used: 𝑎 𝑚𝑜𝑑 𝑏 =Remainder, when a is divided by b. Calculation: 210 ∗ 7 = 1(𝑚𝑜𝑑 13) Multiplying both sides by 8. ⇒ 210.56 = 8(𝑚𝑜𝑑 13) Compare with 210𝑥 = 8(𝑚𝑜𝑑 13) Now x=56 Conclusion: x=56 Question #15 To find: The smallest positive integer that solves the congruences 𝑥 ≡ 1(𝑚𝑜𝑑 6), 𝑥 ≡ 7(𝑚𝑜𝑑 8) Answer: Given information: The congruences are 𝑥 ≡ 1(𝑚𝑜𝑑 6), 𝑥 ≡ 7(𝑚𝑜𝑑 8). Consider the given congruences 𝑥 ≡ 1(𝑚𝑜𝑑 6), 𝑥 ≡ 7(𝑚𝑜𝑑 8) The congruences 𝑥 ≡ 1(𝑚𝑜𝑑 6) means if x is divided by 6, the remainder is 1. So number x is one of the numbers in the following list: 7,13,19,25,31,37,43,... Similarity, the congruence 𝑥 ≡ 7(𝑚𝑜𝑑 8) means if x is divided by 8, the remainder is 7. So the number x is one of the numbers in the following list: 7,15,22,29,36,43,49,56,63,... The smallest number that is found in both the lists is 7, so the smallest number that solves the congruences 𝑥 ≡ 3(𝑚𝑜𝑑7), 𝑥 ≡ 4(𝑚𝑜𝑑5) is 7. ⇒𝑥 =7. Final Statement: The smallest positive integer that solves the congruences 𝑥 ≡ 3(𝑚𝑜𝑑 7), 𝑥 ≡ 4(𝑚𝑜𝑑 5) is x= 7. Question #16 To find: All the natural number Answers for the congruence 4𝑥 ≡ 24 𝑚𝑜𝑑 8 . Answer: It is clear that 24 𝑚𝑜𝑑 8 is same as 0 \𝑏𝑚𝑜𝑑 8 . So, the congruence is rewritten as follows, 4𝑥 ≡ 𝑂 𝑚𝑜𝑑8 When x= 1 the congruence is not satisfied, 4(1) ≡ 0\𝑏𝑚𝑜𝑑8 4 ≡ 0 𝑚𝑜𝑑 8 That is remainder cannot be 0, when it is divided by 8. Similarly, when x= 3 the congruence is not satisfied, 4(3) ≡ 0 𝑚𝑜𝑑8 12 ≡ 0 𝑚𝑜𝑑8 That is remainder cannot be 0 when it is divided by 8. Hence, it can be concluded that all the natural numbers except the odd numbers are Answers. Therefore, the Answer to the congruence 4𝑥 ≡ 24 𝑚𝑜𝑑 8 is (2,4,6,.8,...}. Question #17 Find all solutions of the following linear congruences. Inverses (when required) may not be determined ''by inspection'', but rather must be calculated using the appropriate method with all work shown. 14𝑥 ≡ 6(𝑚𝑜𝑑 31) Answer: Step 1 Given: 14𝑥 ≡ 6(𝑚𝑜𝑑 31) Here a=14; b=6 and N=31 Also gcd(14,31)=1 Hence there can be only one value of x. Since, gcd(a,N)=1, let us multiply by the inverse of ''a'' in order to solve the given linear congruence. The inverse of a=14 is 20. Step 2 Hence, 20 × 14 = 20 × 6(𝑚𝑜𝑑 31) ⇒ 280𝑥 ≡ 120(𝑚𝑜𝑑 31) 𝑥 ≡ 120(𝑚𝑜𝑑 31) 𝑥 ≡ 27(𝑚𝑜𝑑 31) Therefore, x=27 Answer The value of x is 27 Question #18 Solve system of equation by chinese remainder theorem: 𝑥 ≡ 5(𝑚𝑜𝑑 24) 𝑥 ≡ 17(𝑚𝑜𝑑 18) Answer: Step 1 The system of equation 𝑥 ≡ 5(𝑚𝑜𝑑 24) 𝑥 ≡ 17(𝑚𝑜𝑑 18) Solve system of equation by chinese remainder theorem: Chinese Remainder Theorem: Let 𝑚1 , 𝑚2 , 𝑚3 … … 𝑚𝑟 be a collection of pairwise relatively ' integers. Then the system of simultaneous congruences 𝑥 ≡ 𝑎1 (𝑚𝑜𝑑 𝑚1 ) 𝑥 ≡ 𝑎2 (𝑚𝑜𝑑 𝑚2 ) .... 𝑥 ≡ 𝑎𝑟 (𝑚𝑜𝑑 𝑚𝑟 ) has a unique solution modulo 𝑀 = 𝑚1 , 𝑚2 , … … . 𝑚𝑟 for any given integers 𝑎1 , 𝑎2 , … … 𝑎𝑟 . Step 2 Here 𝑚1 = 24, 𝑚2 = 18 𝑔𝑐𝑑(24,18) = 6 ⇒ 𝑔𝑐𝑑(24,18) ≠ 1 Therefore, 𝑚1 and 𝑚2 are not relatively '. Hence, the given system 𝑥 ≡ 5(𝑚𝑜𝑑 24) 𝑥 ≡ 17(𝑚𝑜𝑑 18) has no solution. Question #19 To determine:The decoded message for the following encoded messages. E=456 Answer: Given information: p=17, q=59, and s=3 Explanation: Since, gcd (3,16)=1, there exist integers a and x such that 3a+16x=1. We know that 3(11)-16(2)=1. Thus, a=11. Also, 3(39)-58(2)=1 Thus, b=39. It is given that E=456. So, 𝐸 𝑎 = (456)11 = 10(𝑚𝑜𝑑 17). Also, 𝐸 𝑏 = (456)39 = 42(𝑚𝑜𝑑 59). Now the problem is reduced to solvinga pair of congruences. 𝑥 ≡ 10(𝑚𝑜𝑑 17) 𝑥 ≡ 42(𝑚𝑜𝑑 59) We have, 7(17)-2(59)=1. Thus, x=42.7(17)-10.2(59) is the solution of the above pair of congruences modulo 1003. 𝑥 = 42.7(17) − 10.2(59) 𝑥 = 4998 − 1180 𝑥 = 3818 𝑥 = 809(𝑚𝑜𝑑 1003) Thus, M=809. We conclude that the decoded message for E =456 is HI. Question #20 To determine:The decoded message for the following encoded messages. E=926 Answer: Given information: p=17, q=59, and s=3 Explanation: Since, gcd (3,16)=1, there exist integers a and x such that 3a+16x=1. We know that 3(11)-16(2)=1. Thus, a=11. Also, 3(39)-58(2)=1 Thus, b=39. It is given that E=926. So, 𝐸 𝑎 = (926)11 = 2(𝑚𝑜𝑑 17). Also, 𝐸 𝑏 = (926)39 = 35(𝑚𝑜𝑑 59). Now the problem is reduced to solvinga pair of congruences. 𝑥 ≡ 2(𝑚𝑜𝑑 17) 𝑥 ≡ 35(𝑚𝑜𝑑 59) We have, 7(17)-2(59)=1. Thus, x=35.7(17)-2.2(59) is the solution of the above pair of congruences modulo 1003. 𝑥 = 35.7(17) − 2.2(59) 𝑥 = 4165 − 236 𝑥 = 3929 𝑥 = 920(𝑚𝑜𝑑 1003) Thus, M=920. We conclude that the decoded message for E =926 is IT.