Westonci.ca is the premier destination for reliable answers to your questions, brought to you by a community of experts. Explore our Q&A platform to find reliable answers from a wide range of experts in different fields. Connect with a community of professionals ready to help you find accurate solutions to your questions quickly and efficiently.
Sagot :
Answer:3 Congruence
Congruences are an important and useful tool for the study of divisibility. As we shall see, they are also critical in the art of cryptography.
Definition 3.1 If a and b are integers and n > 0, we write a ≡ b mod n
to mean n|(b − a). We read this as “a is congruent to b modulo (or mod) n. For example, 29 ≡ 8 mod 7, and 60 ≡ 0 mod 15.
The notation is used because the properties of congruence “≡” are very similar to the properties of equality “=”. The next few result make this clear.
Theorem 3.2 For any integers a and b, and positive integer n, we have: 1. a ≡ a mod n.
2. Ifa≡bmodnthenb≡amodn.
3. Ifa≡bmodnandb≡cmodnthena≡cmodn
These results are classically called: 1. Reflexivity; 2. Symmetry; and 3. Transitivity. The proof is as follows:
1. n|(a − a) since 0 is divisible by any integer. Therefore a ≡ a mod n.
2. If a ≡ b mod n then n|(b − a). Therefore, n|(−1)(b − a) or n|(a − b). Therefore, b ≡ a mod n.
3. If a ≡ b mod n and b ≡ c mod n then n|(b−a) and n|(c−b). Using the linear combination theorem, we have n|(b−a+c−b) or n|(c−a). Thus, a≡c mod n.
The following result gives an equivalent way of looking at congruence. It replaces the con-
Step-by-step explanation:
Thanks for using our platform. We're always here to provide accurate and up-to-date answers to all your queries. Thanks for stopping by. We strive to provide the best answers for all your questions. See you again soon. Westonci.ca is here to provide the answers you seek. Return often for more expert solutions.